Na linha de grandes desafios, pensei que este poderia ser interessante.

Neste desafio, usaremos o sistema de número de resíduos (RNS) para executar adição, subtração e multiplicação em números inteiros grandes.

O que é o RNS

O RNS é uma das muitas maneiras que as pessoas desenvolveram para identificar números inteiros. Neste sistema, os números são representados por uma sequência de resíduos (que são os resultados após uma operação de módulo (ou seja, o restante após a divisão inteira)). Neste sistema, cada número inteiro tem muitas representações. Para manter as coisas simples, vamos limitar as coisas para que cada número inteiro seja representado exclusivamente. Eu acho que é mais fácil descrever o que está acontecendo com um exemplo concreto.

Vejamos os três primeiros números primos: 2, 3, 5. No sistema RNS, podemos usar esses três números para representar exclusivamente qualquer número que seja menor que 2 * 3 * 5 = 30 usando resíduos. Tome 21:

21 é menor que 30, então podemos representá-lo usando os resultados após a modificação de 2, 3 e 5. (ou seja, o restante após o número inteiro dividido por 2, 3 e 5)

Identificamos 21 com a seguinte sequência de números inteiros:

21 ~ {21 mod 2, 21 mod 3, 21 mod 5} = {1, 0, 1}

E assim, em nosso sistema RNS, em vez de "21", usaríamos {1,0,1}.

Em geral, dado um número inteiro n , representamos n como { n mod 2, ..., n mod p_k }, em que p_k é o menor primo, de modo que n é menor que o produto de todos os números primos menores ou iguais a p_k .

Outro exemplo, digamos que temos 3412. Precisamos usar 2,3,5,7,11,13 aqui porque 2*3*5*7*11*13=30030considerando 2*3*5*7*11=2310que é muito pequeno.

3412 ~ {3412 mod 2, 3412 mod 3, 3412, mod 5, ..., 3412 mod 13} = {0, 1, 2, 3, 2, 6}

Você percebe que, usando esse sistema, podemos representar números muito grandes de maneira relativamente indolor. Usando resíduos {1, 2, 3, 4, 5, 6, 7, 8, ...}, podemos representar números até {2, 6, 30, 210, 2310, 30030, 510510, 9699690 ...} respectivamente. ( Aqui está a série )

Nossa tarefa

Usaremos esses resíduos para executar +, - e * em grandes números. Vou descrever esses processos abaixo. Por enquanto, aqui estão as especificações de entrada e saída.

Entrada

Você receberá dois números (potencialmente muito grandes) por meio de um argumento stdin ou função. Eles serão dados como cadeias de caracteres de base 10.

Para fins de descrever o problema ainda mais, chamamos a primeira entrada ne a segunda m. Suponha que n> m> = 0 .

Você também receberá +ou -ou *para indicar a operação a ser executada.

Saída

Seja x um número inteiro. Usaremos [ x ] para nos referir à representação RNS descrita acima de x .

Você deve produzir [n] <operator> [m] = [result]

Como executar as operações no RNS

Essas operações são relativamente simples. Dados dois números na notação RNS, para adicioná-los, subtraí-los ou multiplicá-los, simplesmente execute as operações especificadas em componentes e, em seguida, faça o módulo.

ie

{1, 2, 3} + {1, 1, 4} = {(1 + 1) mod 2, (2 + 1) mod 3, (3 + 4) mod 5} = {0, 0, 2}

Observe que, se o número de resíduos usado para representar dois números diferentes não for o mesmo, ao executar operações, será necessário estender o número "mais curto" para que ele tenha o mesmo número de resíduos. Isso segue o mesmo processo. Veja os casos de teste para um exemplo.

O mesmo acontece se o resultado exigir mais resíduos do que qualquer entrada. Então ambas as entradas precisam ser "estendidas".

Detalhes importantes

• Lidaremos com grandes números aqui, mas não arbitrariamente grandes. Seremos responsáveis ​​pelos números até o produto dos 100 primeiros números primos (veja abaixo). Para esse fim, você recebe os primeiros 100 números primos gratuitamente (sem custo de bytes) . Você pode colocá-los em uma matriz chamada pou algo idiomático no seu idioma e subtrair o número de bytes usados ​​para iniciar essa matriz do total final. Obviamente, isso significa que eles podem ser codificados ou você pode usar um built-in para gerá-los.

• Se, por algum motivo, essa for a representação inteira padrão usada no seu idioma. Está bem.

• Você não pode usar nenhum tipo de número inteiro de precisão arbitrária, a menos que seja o padrão do seu idioma. Se for o padrão, você não pode usá-lo para armazenar números inteiros que normalmente não cabem em 64 bits.

• Para ficar claro, cada número inteiro sempre será representado com o menor número de resíduos possível. Isso vale para entrada e saída.

• Eu acho que as outras especificações devem evitar isso, mas para ser redundante: você pode não executar a operação especificada nas entradas e depois alterar tudo para RNS e, em seguida, saída. Você deve alterar as entradas para RNS e, em seguida, executar as operações para produzir a saída.

Casos de teste

1. Entrada:

n = 10
m = 4
+

Saída:

{ 0, 1, 0 } + { 0, 1 } = { 0, 2, 4 }

Explicação:

Primeiro, altere cada número para sua representação RNS, conforme descrito acima:

10 ~ {0,1,0}e 4 ~ {0,1}. Observe que quando queremos fazer a adição de componentes, isso 10tem mais componentes que 4. Portanto, devemos "estender" o número mais curto. Então, escreveremos brevemente 4 ~ {0,1} --> {0,1, 4 mod 5} = {0,1,4}. Agora prosseguimos com a adição e, em seguida, tomamos o módulo.

2. Entrada

n=28
m=18
+

Saída:

 [ 0, 1, 3 ] + [0, 0, 3 ] = [ 0, 1, 1, 4 ]

3. Entrada (eu esmagando meu rosto no teclado)

n=1231725471982371298419823012819231982571923
m=1288488183
*

Saída (dividida em linhas separadas para facilitar a leitura):

[1, 2, 3, 6, 2, 10, 2, 1, 12, 16, 7, 15, 34, 29, 31, 5, 55, 32, 66, 61, 3, 76, 52, 14, 65, 44, 99, 57 ] 
* 
[1, 0, 3, 3, 4, 8, 9, 10, 8, 0 ] 
= 
[1, 0, 4, 4, 8, 2, 1, 10, 4, 0, 17, 7, 27, 21, 44, 51, 56, 9, 6, 9, 12, 0, 52, 36, 43, 68, 99, 24, 96, 39, 96, 66, 125] 

nrequer 28 números primos. mrequer 10. n*mrequer 33.

4. Entrada

n=8709668761379269784034173446876636639594408083936553641753483991897255703964943107588335040121154680170867105541177741204814011615930342030904704147856733048115934632145172739949220591246493529224396454328521288726490
m=1699412683745170450115957274739962577420086093042490863793456500767137147999161679589295549397604032154933975242548831536518655879433595016
-

Saída:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 509]
-
[0, 2, 1, 6, 1, 12, 11, 18, 14, 28, 21, 36, 37, 42, 16, 52, 41, 60, 16, 70, 49, 78, 80, 88, 49, 100, 13, 106, 4, 112, 68, 130, 36, 138, 37, 150, 0, 162, 8, 172, 163, 180, 18, 192, 129, 198, 135, 222, 78, 228, 90, 238, 57, 250, 36, 262, 87, 270, 206, 280, 193, 292, 253, 310, 224, 316, 57, 336, 48, 348]
=
[0, 1, 4, 1, 10, 1, 6, 1, 9, 1, 10, 1, 4, 1, 31, 1, 18, 1, 51, 1, 24, 1, 3, 1, 48, 1, 90, 1, 105, 1, 59, 1, 101, 1, 112, 1, 0, 1, 159, 1, 16, 1, 173, 1, 68, 1, 76, 1, 149, 1, 143, 1, 184, 1, 221, 1, 182, 1, 71, 1, 90, 1, 54, 1, 89, 1, 274, 1, 299, 1, 266, 1, 228, 1, 340, 1, 170, 1, 107, 1, 340, 1, 88, 1, 157, 1, 143, 1, 22, 1, 22, 1, 58, 1, 296, 1, 371, 1, 140]

nusa 100 números primos. musa 70 números primos. n-musa 99 números primos.

Eu os verifiquei usando a ChineseRemimplementação interna do teorema chinês Remainder no GAP (que basicamente pega números RNS e os altera para a base 10 inteiros). Eu acredito que eles estão corretos. Se algo parecer suspeito, entre em contato.

Para quem se importa, o produto dos 100 primeiros números primos é:

471193079990618495316248783476026042202057477340967552018863483961641533584503
422120528925670554468197243910409777715799180438028421831503871944494399049257
9030720635990538452312528339864352999310398481791730017201031090

Esse número é 1 maior que o número máximo que podemos representar usando o sistema fornecido (e a limitação de 100 primos).

Um pouco relacionado

GAP

Alguns antecedentes: admito que, quando criei essa pergunta, há muitos meses, eu não tinha um método para resolver a parte difícil dessa questão: determinar o número correto de números primos a serem usados. Temos muitas pessoas muito inteligentes neste site, e eu realmente esperava que alguém descobrisse uma maneira de fazê-lo rapidamente. No entanto, como isso não aconteceu, eu nem tinha certeza de que era realmente possível resolver esse problema. Então, eu tive que dedicar um tempo para criar um método. Acredito que o que fiz não viole nenhuma das regras deste desafio, é claro que eu adoraria que isso fosse verificado.

Também me arrependo um pouco da escolha do código-golfe, porque as soluções são um pouco mais profundas do que normalmente se ajustariam ao formato da tag. Dito isto, para seguir as regras do site, há uma versão "golfed" da minha solução na parte inferior deste post.

Código

### The first 100 primes;
primes := Primes{[1..100]};

### In many of the functions below, the 'string' variable is a string of digits
###


### Returns the 'index' digit of 'string' as an integer
GetValueAsInt := function(string, index) 
    return IntChar(string[index]) - 48;
end;

### Used in the 'modulus' function. See that comment for more information. 
### Calculates the contribution to the modulus of a digit 'digit' in the 10^power place.
### 'integer' is the modulus
digit_contribution := function(digit, integer, power)
    local result, i;
    result := 1;
    for i in [0..power-1] do
        result := ( result * (10 mod integer) ) mod integer;
    od;
    result := (result * (digit mod integer) ) mod integer;
    return result;
end;

### This modulus function is used to calculate the modulus of large numbers without storing them
##### as large numbers.
### It does so by breaking them into digits, and calculating the contribution of each digit.
### e.g. 1234 mod 5 = (1000 mod 5)(1 mod 5) + (200 mod 5)(2 mod 5) + (10 mod 5)(3 mod 5) + (4 mod 5)
### It actually mods after every calculation to ensure that we never get a number larger
##### than the modulus ('integer') squared, which will never be even close to 10^64-1
modulus := function(string, integer)
    local i, result, digit, len;
    len := Length(string);
    result := 0;
    for i in [1..len] do
        digit :=  IntChar(string[i]) -48;
        result := ( result + digit_contribution(digit, integer, len-i) )  mod integer;
    od;
    return result;
end;

### This returns the product of the first i-1 primes (mod j). It must not (and does not)
##### ever store an integer larger than 2^64-1
phi_i := function(i,j)
    local index, result;
    result := 1;
    for index in [1..i-1] do
        result := ( result * primes[index] ) mod primes[j];
    od;
    return result;
end;

### Calculates the first residues of 'string' mod the first 100 primes
get_residues := function(string) 
    local p, result;
    result := [];
    for p in primes do
        Add( result, modulus(string, p) );  
    od; 
    return result;
end;

### Gets the ith element in the partial_chinese array, given the previous elements
### See the explanation section and partial_chinese function for more info
get_partial_i := function( i, residues, previous_array )
    local index, result;
    result := residues[i];
    for index in [1..Length(previous_array)] do
        result := ( result - previous_array[index]*phi_i(index,i) ) mod primes[i]; 
    od;     
    result := ( result / phi_i(i,i) ) mod primes[i];
    return result;
end;

### returns an array such that the sum of prod_primes(i)*array[i] is equal to the integer value
##### that is represented by the residues. (It basically just does the CRT without
##### actually summing everything.) prod_primes(i) is the product of the first i-1 primes 
### See the explanation for a bit more info
### This is what allows us to determine the minimal number of primes to represent a RNS number
partial_chinese := function( string )
    local array, i, residues;
    residues := get_residues(string);
    array := [];        
    for i in [1 .. Length(primes)] do
        Add( array, get_partial_i( i, residues, array ) );
    od;
    return array;   
end;

### Same as partial_chinese but takes input in a different form.
partial_chinese_from_residues := function(residues)
    local array, i;
    array := [];        
    for i in [1 .. Length(primes)] do
        Add( array, get_partial_i( i, residues, array ) );
    od;
    return array;
end;

### gives you the number of primes needed to represent an integer. Basically asks how 
##### many trailing zeros there are in the chinese array.
get_size := function(string)
    local array, i, len, result;
    array := partial_chinese(string);
    len := Length(array);
    for i in [0..len-1] do
        if  not (array[len-i] = 0) then
            return len -i;
        fi; 
    od; 
    Print("ERROR: get_size().\n");
    return 0;
end;

### Same as above but with different input format
get_size_from_residues := function(residues)
    local array, i, len, result;
    array := partial_chinese_from_residues(residues);
    len := Length(array);
    for i in [0..len-1] do
        if  not (array[len-i] = 0) then
            return len -i;
        fi; 
    od; 
    Print("ERROR: get_size().\n");
    return 0;
end;

### the actual function. inputs are all strings
f := function(in1, in2, opperation)
    local residues_1, residues_2, residues_result, i;
    residues_1 := get_residues(in1);
    residues_2 := get_residues(in2);
    residues_result := [];
    if opperation = "+" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] + residues_2[i] ) mod primes[i]);
        od;     
    elif opperation = "*" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] * residues_2[i] ) mod primes[i]);
        od;     
    elif opperation = "-" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] - residues_2[i] ) mod primes[i]);
        od;     
    fi;
    Print(residues_1{[1..get_size(in1)]}, " ", opperation, " ", residues_2{[1..get_size(in2)]}, " = ", residues_result{[1..get_size_from_residues(residues_result)]} );
end;

Explicação:

Para começar, calculamos todos os 100 resíduos para ambas as entradas. Fazemos isso com a modulusfunção no código. Tentei tomar cuidado para usar a modfunção interna após cada etapa. Isso garante que nunca tenhamos um número maior que 540^2, que seja 1 a menos que o centésimo primo ao quadrado.

Depois de termos todos os resíduos, podemos executar a operação especificada e modcada entrada novamente. Agora, temos um designador exclusivo para o resultado, mas precisamos determinar o número mínimo de entradas que precisamos usar para representar o resultado e cada uma das entradas.

Descobrir quantos resíduos realmente precisamos é de longe a parte mais difícil desse problema. Para determinar isso, realizamos a maioria das etapas do Teorema do Restante Chinês (CRT). No entanto, obviamente temos que fazer modificações para não acabar com números muito grandes.

Let prod(i)Ser a soma dos primeiros i-1números primos. Por exemplo,

prod(1) = 1
prod(2) = 2
prod(3) = 6
prod(4) = 30
etc

Let XSer um número inteiro. Let {r_i}Ser os resíduos de X, isto é

r_i = X mod p_i

Onde p_iestá o ith th prime. Isto é para o 1<i<=100nosso caso.

Agora vamos usar o CRT para encontrar uma sequência em {u_i}que a soma acima ide prod(i) * u_iseja igual a X. Observe que cada u_ium também é tecnicamente um resíduo, como u_i < p_i. Além disso, se X < prod(i)então u_i = 0. Isto é de importância crítica. Isso significa que, examinando os zeros à direita, podemos determinar quantos resíduos r_irealmente precisamos representar Xno RNS.

Se você deseja examinar algumas seqüências de u_i, a partial_chinesefunção retornará a u_isequência.

Brincando com o CRT, consegui encontrar uma fórmula recursiva para os u_ivalores, resolvendo a questão de determinar quantos resíduos precisamos.

A fórmula é:

u_i = [ r_i - SUM ] / prod(i)       (mod p_i)

Onde SUMestá a soma j in [1,i)de u_j * prod(i).

Obviamente, prod(i)em alguns casos não pode ser calculado porque é muito grande. Para esse fim, usei a phi_ifunção Esta função retorna prod(j) (mod p_i). É moda cada passo, portanto, na verdade, nunca calculamos algo muito grande.

Se você está curioso de onde vem essa fórmula, eu recomendaria trabalhar alguns exemplos de CRT, que podem ser encontrados na página da wikipedia .

Finalmente, para cada entrada e também para nossa saída, calculamos a u_isequência e depois determinamos os zeros à direita. Então jogamos fora muitos r_ideles no final das seqüências de resíduos.

Código "Golfed", 2621 bytes

primes:=Primes{[1..100]};GetValueAsInt:=function(string,index)return IntChar(string[index])-48;end;digit_contribution := function(digit, integer, power)local result, i;result:=1;for i in [0..power-1] do result := ( result * (10 mod integer) ) mod integer;od;result:=(result*(digit mod integer) ) mod integer;return result;end;modulus:=function(string, integer)local i,result,digit,len;len:=Length(string);result:=0;for i in [1..len] do digit:= IntChar(string[i])-48;result:=(result+digit_contribution(digit,integer,len-i)) mod integer;od;return result;end;phi_i:=function(i,j)local index,result;result:=1;for index in [1..i-1] do result:=(result*primes[index] ) mod primes[j];od;return result;end;get_residues:=function(string) local p,result;result:=[];for p in primes do Add(result,modulus(string,p));od;return result;end;get_partial_i:=function(i,residues,previous_array)local index,result;result:=residues[i];for index in [1..Length(previous_array)] do result:=(result-previous_array[index]*phi_i(index,i) ) mod primes[i];od;result:=(result/phi_i(i,i)) mod primes[i];return result;end;partial_chinese:=function(string)local array,i,residues;residues:=get_residues(string);array:=[];for i in [1 .. Length(primes)] do Add(array,get_partial_i(i,residues,array));od;return array;end;partial_chinese_from_residues:=function(residues)local array,i;array:=[];for i in [1..Length(primes)] do Add(array,get_partial_i(i,residues,array));od;return array;end;get_size:=function(string)local array,i,len,result;array:=partial_chinese(string);len:=Length(array);for i in [0..len-1] do if not (array[len-i] = 0) then return len-i;fi;od;Print("ERROR: get_size().\n");return 0;end;get_size_from_residues:=function(residues)local array,i,len,result;array:=partial_chinese_from_residues(residues);len:=Length(array);for i in [0..len-1] do if not (array[len-i]=0) then return len-i;fi;od;Print("ERROR: get_size().\n");return 0;end;f:=function(in1,in2,opperation)local residues_1,residues_2,residues_result,i;residues_1:=get_residues(in1);residues_2:=get_residues(in2);residues_result:=[];if opperation = "+" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]+residues_2[i] ) mod primes[i]);od;elif opperation = "*" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]*residues_2[i])mod primes[i]);od;elif opperation = "-" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]-residues_2[i]) mod primes[i]);od;fi;Print(residues_1{[1..get_size(in1)]}, " ", opperation, " ", residues_2{[1..get_size(in2)]}, " = ", residues_result{[1..get_size_from_residues(residues_result)]} );end;

Mathematica, não jogou golfe

rns[d_,l_]:=Table[Reap[
    FoldPairList[Sow@QuotientRemainder[10#+#2,Prime@i]&,0,d]
  ][[2,1,-1,2]],{i,l}];
plus[a_,b_]:=Mod[a+b,Prime@Range@Length@a];
subtract[a_,b_]:=Mod[a-b,Prime@Range@Length@a];
times[a_,b_]:=Mod[a b,Prime@Range@Length@a];
mag[f_]:=LengthWhile[FoldList[#/#2&,f,Prime@Range@100],#>1.1&];
ext[m_,n_,i_]:=Fold[Mod[1##,Prime@i]&,m,Prime@Range@n];
multi[e_,p_,t_]:=Tr@Position[Mod[e Range@p,p],p-t];
appx[d_] := N@FromDigits[{d~Take~UpTo[6], Length@d}]

• A função rns[d_,l_]converte um número inteiro de base 10 dem um número inteiro RNS de comprimento l.

• A função plus/ times/ subtractadiciona / multiplica / subtrai um número inteiro do RNS para / de outro, ambos com o mesmo comprimento.

• A função mag[f_]estima a magnitude aproximada do número de ponto flutuante fem termos do limite inferior do comprimento de sua representação RNS.

• A função ext[m_,n_,i_]descobre o restante da divisão do produto de me Prime[Range@n]por Prime[i].

• A função multi[e_,p_,t_]fornece o menor multiplicador mque satisfazDivisible[m*e+t,p]

• A função obtém appx[d_]os primeiros 6dígitos de um número inteiro decimal e fornece seu valor aproximado de ponto flutuante.

Com a ajuda das funções acima, agora somos capazes de resolver um problema complicado - para determinar a duração do resultado .

Primeiro, preciso esclarecer que não é uma tarefa fácil determinar o comprimento do RNS de um número inteiro. Para números inteiros pequenos, podemos compará-los diretamente com o produto de números primos. Mas para números inteiros muito grandes, uma vez que é proibido calcular o produto de números primos infinitamente preciso, essa comparação não funciona mais.

Por exemplo, dado que o produto de prime 1to 30é 3.16*10^46, o comprimento RNS dos números inteiros ao redor 3.16*10^46pode ser 29ou 30. A função magfornecerá 29como referência para esses números inteiros, mostrando que ambos 29e 30são possíveis.

Depois de conhecer a magnitude, simplesmente representamos o número inteiro de acordo com essa magnitude diretamente, na esperança de calcular seu comprimento real. O truque aqui é adicionar alguns novos números ao número original e modificar sua representação RNS, até que a representação seja zero.

Por exemplo, mag[211.]é 4, e sua 4representação de comprimento é {1, 1, 1, 1}.

step 1:   {1,1,1,1} -> {0,2,2,2}  by adding  (1) * 1 = 1
step 2:   {0,2,2,2} -> {0,0,1,6}  by adding  (2) * 2 = 4
step 3:   {0,0,1,6} -> {0,0,0,2}  by adding  (2*3) * 4 = 24
step 4:   {0,0,0,2} -> {0,0,0,0}  by adding  (2*3*5) * 6 = 180
step 5:   calculate 211 + (1 + 4 + 24 + 180) ~ 420

Ao adicionar algum número, aumentamos 211para o menor número que é divisível por 210( 2*3*5*7). E agora concluímos que o número original é maior que 210, uma vez que 420é igual a "aproximadamente" duas vezes de 210. Não é difícil imaginar que, se começarmos 209, o número final é "aproximadamente" 210.

A função length[f_,n_]pega o valor do ponto flutuante fpara estimar a magnitude e corrige-o com base na sua representação RNS n.

length[f_,n_]:=With[{g=mag@f},
    g+If[#==0,1,Round[(#+f)/Times@@Prime@Range@g]-1]&[
      FoldList[Times,1.,Prime[Range[g-1]]].
      FoldPairList[
        Block[{i=#2,m},
          {m=multi[ext[1,i-1,i],Prime@i,Part@##],rnsPlus[#,ext[m,i-1,#]&/@Range[g]]}
        ]&,n,Range[g]]]]

A função rnsOperation[a_,b_,op_,rnsop_]fornece rnsop[a,b]e opcorresponde às operações normais usadas para obter resultados aproximados com base nos valores de ponto flutuante.

rnsOperation[a_,b_,op_,rnsop_]:=Block[{c=op[appx@a,appx@b],m},
    m=mag[c];m=length[c,rnsop[rns[a,m],rns[b,m]]];rnsop[rns[a,m],rns[b,m]]]

Exemplo

rnsOperation[
    IntegerDigits@1231725471982371298419823012819231982571923,
    IntegerDigits@1288488183,
    Times, times]
(* {1,0,4,4,8,2,1,10,4,0,17,7,27,21,44,51,56,9,6,9,12,0,52,36,43,68,99,24,96,39,96,66,125} *)

Python 3 , 435 bytes

Esse desafio está na minha lista de desejos por um tempo, mas é apenas recentemente que: a) dedico tempo e atenção para realmente tentar uma resposta; eb) realmente testou minha idéia para calcular o tamanho dos números (e, portanto, o número de primos comparando-o com o tamanho dos primoriais) usando alguma combinação profana de logaritmos e o Teorema Chinês de Restantes. Infelizmente, trabalhar com logaritmos enquanto tentava determinar o número de números primos que, por exemplo, large_primorial + 3requer, significava que eu estava tendo que encontrar maneiras de solucionar problemas de ponto flutuante.

E assim, este é um porto da resposta de Liam .

Experimente online!

from functools import reduce as R
G=range
d=lambda s:[R(lambda z,c:(z*10+int(c))%q,s,0)for q in p]
h=lambda j,i:R(lambda z,q:z*q%p[i],p[:j],1)
def s(r):
 a=[];z=99
 for i in G(100):
  P=p[i];u=r[i]
  for j in G(len(a)):u=(u-a[j]*h(j,i))%P
  for k in G(1,P):
   if h(i,i)*k%P<2:break
  a+=u*k%P,
 while(a[z]<1)*z:z-=1
 return r[:z+1]
def f(a,b,n):u=d(a);v=d(b);print(s(u),n,s(v),'=',s([eval(str(u[i])+n+str(v[i]))%p[i]for i in G(100)]))

Explicação

Enquanto tentava portar a resposta de Liam, eu pessoalmente achei que algumas das explicações dadas eram confusas, portanto essa é minha tentativa de explicar seu algoritmo.

Primeiro, obtemos os resíduos de ne m.

res1 = get_residues(n)
res2 = get_residues(m)

Isso envolve transformar todos os dígitos das seqüências de entrada e transformá-los em números módulo cada um de nossos números primos, por exemplo, para 28, teríamos [(20 + 8) mod 2, (20 + 8) mod 3, (20 + 8) mod 5, etc]

def get_residues(string):
    result = []
    for p in primes:
        result.append(reduce(lambda z, c:(z*10+int(c)) % p, string, 0))

Em seguida, adicionamos, multiplicamos ou subtraímos os resíduos aos pares usando eval()

result = []
for i in range(len(primes)):
    result.append((eval(str(res1[i]) + op + str(res2[i])) % primes[i])

Em seguida, obtemos os tamanhos de nossos resíduos, ou seja, o número mínimo de primos de que precisamos.

size1 = get_size(res1)
size2 = get_size(res2)
size3 = get_size(result)

Obter os tamanhos é a parte mais complicada e que exige mais código. Usamos a partial_chinesefunção, que nos leva a nossa sequência de u_ipara determinar o tamanho com. Mais u_iem um momento.

def get_size(residues):
    array = partial_chinese(residues)
    size = len(residues)-1
    while array[size] == 0 and size:
        size -= 1
    return size+1  # to prevent off-by-one errors from 0-indexing

A sequência u_ié calculada pegando cada resíduo r_i, subtraindo a soma u_j * primorial(j) for j in [1, i)e depois dividingpor primorial(i)todo o módulo primes[i]. Isto é u_i = (r_i - SUM) / primorial(i). Mais sobre nossas funções primárias e de divisão em um momento.

def partial_chinese(residues):
    array = []
    for i in range(len(primes)):
        array.append(get_partial_i(i, residues, array))
    return array

def get_partial_i(i, residues, previous_array):
    result = residues[i]
    for j in range(len(previous_array)):
        result = (result - previous_array[j] * phi_i(j, i)) % primes[i]
    result = result * inverse(phi_i(i, i), primes[i]) % primes[i]
    return result

phi_i(j, i)calcula primorial(j) mod primes[i]. O módulo de divisão qualquer primo pé facilmente implementado verificando-se inversos multiplicativos manualmente, pois podemos ter certeza de que qualquer possível u_ié0 <= u_i < p coprime para ep e, portanto, um inverso multiplicativo.

def phi_i(j, i):
    return reduce(lambda z, q: z * q % primes[i], primes[:j], 1)

def inverse(n, p):
    for i in range(1, p):
        if n * i % p == 1:
            return i

Com tudo isso, imprimimos nossa string e pronto.

print(res1[:size1], op, res2[:size2], "=", result[:size3])

Qual é o próximo

Foi divertido de implementar. Ainda quero ver se posso usar logaritmos de alguma maneira em outra resposta. E eu gostaria de implementar esse código ou algo parecido em uma linguagem de golfe funcional, como APL ou Jelly. Todas e quaisquer sugestões e correções de golfe são bem-vindas!