大数的模数

Question

我正在尝试计算 T-SQL 中非常大的数（> 38 位）的模数。

我曾经将我的变量转换为数字，但现在这个数字太大了，它抛出了一个错误：算术溢出错误将 varchar 转换为数字数据类型。

例如，我想知道我应该如何继续得到这个结果： 17448000012524221015281629272289115277 % 97（在这种情况下结果应该是 1）

感谢您的帮助。

Answer 1

您可以根据模属性将长整数拆分为多个部分来计算模数：

(a + b) mod n = [(a mod n) + (b mod n)] mod n.

和

ab mod n = [(a mod n)(b mod n)] mod n.

17448000012524221015281629272289115277 = 17448000012524221015281629 * 1000000000000 + 272289115277

所以

select ((17448000012524221015281629 % 97)*(1000000000000 % 97) + 272289115277 % 97) % 97 as modulo

Answer 2

尝试：

DECLARE @Dividend VARCHAR(100) = '17448000012524221015281629272289115277'
DECLARE @Divisor BIGINT = 97

DECLARE @ChunkSize INT = 10  -- Must be >= 1 and < roughly Log10(bigint max / @Divisor)
DECLARE @Base BIGINT = CONVERT(BIGINT, '1' + REPLICATE('0', @ChunkSize))  -- 10 ^ ChunkSiae
DECLARE @PaddedSize INT = CEILING(LEN(@Dividend) * 1.0 / @ChunkSize) * @ChunkSize 
DECLARE @PaddedValue VARCHAR(100) = RIGHT(REPLICATE('0', @ChunkSize) + @Dividend, @PaddedSize)

DECLARE @Remainder BIGINT = 0
WHILE (LEN(@PaddedValue) > 0)
BEGIN
    DECLARE @PartValue BIGINT = CONVERT(BIGINT, LEFT(@PaddedValue, @ChunkSize))
    SET @Remainder = (@Remainder * @Base + @PartValue) % @Divisor
    SET @PaddedValue = STUFF(@PaddedValue, 1, @ChunkSize, '')
END

SELECT @Remainder

如果分红值可能为负，则需要提取符号并调整所得余数。

Answer 3

这里的解决方案是，当数字太大时，将其切割以计算模数97。

问题是每个 97 的 10 次方都会有 0 作为模数 97

    970%97=0
   9700%97=0
  97000%97=0
 970000%97=0

例如
( 12345 )%97 可以拆分为
( (123 %97)*100 + 45 )%97

select *

, case 
  when len(bignum)>=38
  then ((cast(left(bignum, len(bignum)-18) as decimal(38,0))%97)
       * cast(power(1e1,18) as decimal(38,0))
       + cast(right(bignum, 18) as decimal(38,0)))%97
  else cast(bignum as decimal(38,0))%97
  end as mod97

from (values
('17448000012524221015281629272289115277'), 
('100'), 
('97000000000000000000000000000000000000000000000000000001')
) q(bignum);

bignum	mod97
17448000012524221015281629272289115277	77
100	3
97000000000000000000000000000000000000000000000000000001	1

db<>fiddle here

大数的模数

Modulus of a large number

sql

tsql

modulo