I want to perform Multiplication and Division of two 128 bit unsigned integers in a system that doesn't contain floats
Currently I am facing a problem where when I multiply two numbers 5e20 * 5e20 = 2.5E41
it overflows from 128 bit max range that can only contain a maximum number with 39 digits. So I cannot multiply two very big numbers due to which my precision is reduced. I want precision up to 16 decimal places.
If I perform division of numbers as well 10 / 3 = 3.3333333
I get only 3 because my system doesn't contain floating point so floating part is ignored. In order to achieve the precision, I scale up my dividend by multiplying it 1e16 to get 16 decimal precision.
I also tried to use scientific notation to solve my precision so that I can multiply and divide 2.5/4 or 2.5x4
by writing 25x10^-1 and 4x10^0 but due to this, my multiplication remains in scale-down format while my division remains in scaled-up form 2.5/4 = 6.25E16 * 10^-1 (scaled up)2.5*4 = 100 * 10^-1 (scaled down)
How can I solve this problem? What approach should I use?
There is no easy answer, you'll have to either implement operations for 256 bits integers (still not going to help your division, where you should use a scaling factor to represent your numbers), implement operations for a fixed point representation, or operations for a floating point representation (mantissa + exponent), none of which are trivial endeavors.
For a 256 bits arithmetic, someone had created a proof of concept (but not battle tested): https://github.com/KStasi/clarity-uint256-lib. She was using 4 uint64 to be able to use uint128 arithmetic without overflows.
Here's a 16 bits multiplication using an 8 bit multiplier:https://www.techiedelight.com/multiply-16-bit-integers-using-8-bit-multiplier/. You'll need to do similar things with 128 bit numbers.
Similarly, here are some pointers for doing a division with lower precision arithmetic: http://www.mattmillman.com/mcs-48-the-quest-for-16-bit-division-on-the-8-bit-cpu-which-cant-divide-anything/
Instead of using a scaling factor, an other approach would be to use fixed point representation. See https://en.wikipedia.org/wiki/Fixed-point_arithmetic for theory, and https://schaumont.dyn.wpi.edu/ece4703b20/lecture6.html for more practical considerations (some DSPs have the same issue, they only have integer operations).