How to do "fixed size" (wrapping) math in Python?

[AlexanderWulf]

Hello.

I want to port an existing algorithm to Python. Original code is written in C and uses fixed-size integer types, such as uint64_t. The computation relies heavily on the "wrapping" behavior of C integer types: If we add or multiply two uint64_t values, we get an uint64_t containing the result of the addition or multiplication truncated to the lowest 64-Bit; the "high" bits are discarded implicitly. Without this truncation, which needs to happen in every arithmetic operation (and there are a lot of them!), the result would not be "correct", with respect to the original algorithm.

(Note: Truncating only the final result, while leaving all intermediate values at larger precision, would not give the "expected" outcome)

So, how can I get this behavior in Python? I understand that Python uses variable-size integer. This means that, for example, multiplying two 64-Bit values results in ~128-Bit value. Of course, I could simply apply "modulus 2^64" after every multiplication or addition. But I think this would result in very cluttered code. And it also would be highly inefficient! I mean, every multiplication would create a ~128-Bit intermediate result which then needs to be "truncated" to 64-Bit, throwing away the intermediate result. Also, the required "modulus" operation is known to be very slow. Is there a "better" (less cluttered, more efficient) way to accomplish the required "fixed size" (wrapping) integer math in Python? is there a recommended support library for this?

I read about ctypes library. It has fixed-sized types, such as c_ulonglong, which seems to be exactly what I need. Unfortunately, I couldn't figure out how to multiply two c_ulonglong values, as Python gives error "unsupported operand" when trying to multiply a c_ulonglong with another c_ulonglong

Thank you!

[deanhystad]

Why not use the C code?

[AlexanderWulf]

Because we need to use the algorithm in Python project and therefore need a pure Python implementation. I did not make this decision

There is reference implementation in C, but we can't use it.

[deanhystad]

Sorry, I don't understand the need for "pure python". Much (most) of Python is C libraries. Why not call this code from Python?

[AlexanderWulf]

To my understanding, only CPython is written in C, and only the "core" interpreter is written in C. The actual program code and the libraries that we install via pip are "portable" Python code, right? So, you suggest we kind of implement the algorithm directly on the level of the interpreter? Wouldn't this require to maintain our own "fork" of CPython? Anyway, I think this is way beyond the scope of the project, and what I can do. Also I think we need a "portable" solution that works on different platforms and different Python interpreters. I think there's interpreters that don't use C at all...

So, given that we need to port the algorithm to Python, is there any recommended/idiomatic way to do "fixed-size" (wrapping) arithmetic

[deanhystad]

Many of the most popular packages are written in C, with Python code as a wrapper. Pandas is not written in Python. Numpy is not written in Python. Matplotlib is not written in Python. Pygame is not written in Python.....

Open up the site packages folder. Look for the name of a Python package you use frequently. Dig down in the folders and pretty soon you'll start seeing .dll, .so, .a file extensions. When you pip install these packages they either download the correct libraries for your platform or compile the libraries on your computer.

[AlexanderWulf]

Well, thanks for the info. That's all interesting, but I think it is not what I need.

Look, I have "reference" code in C. That's just a simple C function. I could add a main() function to call the function that implements the algorithm and then compile an .exe file. But I don't see how that helps me with the Python project, or how I would invoke that from the Python code. And, even if I somehow could create an .exe (or .dll) file that can be invoked from Python code, it would not really solve the task. We need an implementation of the algorithm as "portable" Python code that works on different platforms and, ideally, with all Python interpreters (not only CPython). I think porting the code actually shouldn't be too hard, if it wasn't for the "mod 2^64" arithmetic stuff. So, thanks again for your suggestions so far, but can we please discuss the original question?

So, given that we need to port the algorithm to Python, is there any recommended/idiomatic way to do "fixed-size" (wrapping) arithmetic ???

I mean, a lot of algorithms, like hash functions and stuff, are defined with "fixed-size" (wrapping) arithmetic. So, this doesn't seem like an unusual requirement. How is it usually done in Python?

Thank you!

[deanhystad]

When you create a wheel (a package distribution that you can install using pip), you include instructions on how to handle things like installing libraries. You could inlcude your C code as source, and have the wheel compile the code to make the library. This is frequently done. The result is a portable, native library.

You may not like the answer, but this is how this kind of thing is done in Python.

Another option is to piggyback off one of the packages that calls a C library to do math, line numpy.

import numpy as np

x = np.ubyte(42)
y = x
for _ in range(10):
    print(y)
    y += x

Output:
42
84
126
168
210
252
c:\Users\djhys\Documents\python\musings\junk.py:7: RuntimeWarning: overflow encountered in scalar add
  y += x
38
80
122
164

The addition is actually happening in a numpy C library. You can turn off the warning. Now your packages forces users to install numpy. Which, by the way, you can make happen automatically by adding that package to your wheel.

[deanhystad]

I read about ctypes library. It has fixed-sized types, such as c_ulonglong, which seems to be exactly what I need. Unfortunately, I couldn't figure out how to multiply two c_ulonglong values, as Python gives error "unsupported operand" when trying to multiply a c_ulonglong with another c_ulonglong Confused

ctypes is a library that makes it easier to call C functions. It makes C-like data types, but it does not provide C math support. You would use ctypes to call your fixed size integer math equation from the C library that was installed as part of your portable Python package.

Some documentation about how you call C functions from Python.

https://docs.python.org/3/extending/extending.html

[PyDan]

If you have the C code, or C++, it may be possible to write your own type and expose it to python, do the math on the C++ side
I do this with boost::python, classes like vector and matrix, provide the operators, do the math in C++ return the results to python

pseudo code

    class_<PyLargeInteger>("LargeInteger")
        .def(init<int64_t&>())
        .def("__eq__", &PyLargeInteger::func)
        .def("__ne__", &PyLargeInteger::func)
        .def("__mul__", &PyLargeInteger::func)
        .def("__rmul__", &PyLargeInteger::func)
        .def("__truediv__", &PyLargeInteger::funcd)
        .def("__itruediv__", &PyLargeInteger::func)
        .def("__add__", &PyLargeInteger::func)
        .def("__iadd__", &PyLargeInteger::func)
        .def("__sub__", &PyLargeInteger::func)
        .def("__isub__", &PyLargeInteger::func)
        .def("__str__", &PyLargeInteger::func)
        .def("__repr__", &PyLargeInteger::func)
        ;