Algorithm for precisely getting the remainders of large numbers?

Help and Feedback Scripting Support
#1

I wanted to find the remainder of a large numbers (say 6,805 * 10^38) by dividing another large number (say 8,507 * 10^38). Is there any algorithm or option for doing this precisely?
However doing 680564693277057719623408366969033850880 % 85070591730234615847396907784232501249 returns 85070551165415408562502803963439480832 when the correct answer is 85070551165415408691630012479406342137 as I’m getting the remainder of a data type float. Is there any algorithm or option to precisely get the remainder of this?
Something like C#'s BigInteger (or a ‘ulong’ data type or something like that):

using System;
using System.Numerics;
public class Program
{
	public static void Main()
	{
		BigInteger a = BigInteger.Parse("680564693277057719623408366969033850880");
		BigInteger b = BigInteger.Parse("85070591730234615847396907784232501249");
		Console.WriteLine(a % b);
	}
}

Which returns:

85070551165415408691630012479406342137

#2

Alright, I decided to create an array of little-endian base 16 numbers to bypass the float data type {0, 1, 2, 3, 15} the algorithm I’m using is this:

But I don’t completely get this algorithm (Not the best at maths), but here’s what I’ve tried

-- 1.260.257 / 37 (base 10)
local n = { 7, 5, 2, 0, 6, 2, 1 };
local m = { 7, 3 };
local b = 10;
--
local k, l, q, r = #n, #m, { }, { };
if k < l then
	q = { 0 };
	r = m;
else
	for i = k - 1, 1, -1 do
		local qi, di, ai, beta_i = q[i], n[i], n[i - 1], q[i - 1];
		print(i, b * (r[i + 1] or 0) + n[i - l + 2])
	end;
end;
#3

I might look into this in greater depth later but I’m actually just curious on a surface level as to what the use case(s) is (are), and why you can’t use modulus %. (or extrapolating, arithmetic inbuilts) for such a large value.

#4

why you can’t use modulus % . (or extrapolating, arithmetic inbuilts) for such a large value.

Lua uses float (or real, IIRC) data type to store their numbers thus 2^53 (9.007.199.254.740.992) is the highest number you can get without it getting weird thus whenever I do something like 680564693277057719623408366969033850880 % 85070591730234615847396907784232501249, it returns an incorrect value, in fact (2 ^ 53) + 1 == (2 ^ 53) returns true. I wanted a precise algorithm that gets the remainder correctly of an arbitrary large number.

#5

I decided to change the algorithm as I don’t really get that algorithm and no one really helped me.
Is this algorithm I’m looking for?
https://referencesource.microsoft.com/#System.Numerics/System/Numerics/BigInteger.cs

       public static BigInteger DivRem(BigInteger dividend, BigInteger divisor, out BigInteger remainder)
        {
            dividend.AssertValid();
            divisor.AssertValid();
 
            int signNum = +1;
            int signDen = +1;
            BigIntegerBuilder regNum = new BigIntegerBuilder(dividend, ref signNum);
            BigIntegerBuilder regDen = new BigIntegerBuilder(divisor, ref signDen);
            BigIntegerBuilder regQuo = new BigIntegerBuilder();
 
            // regNum and regQuo are overwritten with the remainder and quotient, respectively
            regNum.ModDiv(ref regDen, ref regQuo);
            remainder = regNum.GetInteger(signNum);
            return regQuo.GetInteger(signNum * signDen);
        }

Which the moddiv leads to this, Reference Source

   public void ModDiv(ref BigIntegerBuilder regDen, ref BigIntegerBuilder regQuo) {
      if (regDen._iuLast == 0) {
        regQuo.Set(DivMod(regDen._uSmall));
        NumericsHelpers.Swap(ref this, ref regQuo);
        return;
      }
      if (_iuLast == 0)
        return;
 
      ModDivCore(ref this, ref regDen, true, ref regQuo);
    }

    public uint DivMod(uint uDen) {
      AssertValid(true);
 
      if (uDen == 1)
        return 0;
      if (_iuLast == 0) {
        uint uTmp = _uSmall;
        _uSmall = uTmp / uDen;
        return uTmp % uDen;
      }
 
      EnsureWritable();
 
      ulong uu = 0;
      for (int iv = _iuLast; iv >= 0; iv--) {
        uu = NumericsHelpers.MakeUlong((uint)uu, _rgu[iv]);
        _rgu[iv] = (uint)(uu / uDen);
        uu %= uDen;
      }
      Trim();
      return (uint)uu;
    }
#6

Getting the remainders of large numbers is actually an active field of research in the mathematics and computational industries. It is theorised that a perfect algorithm for solving remainders in a feasible amount of time when the numbers are mathematically large is impossible and forms the backbone for a lot of encryption techniques.

This causes a lot of debate around the introduction of quantum computers, with the fact that Shor’s algorithm becomes polynomial in time complexity when running on a quantum machine, will be able to find integer factors of large numbers tractably.

I personally find it a really interesting field of research and as you’ve expressed a desire to form this algorithm I think it would interest you quite a lot also.

1 Like