W obliczu wielu wyzwań pomyślałem, że to może być interesujące.

W tym wyzwaniu będziemy używać systemu liczb resztkowych (RNS) do wykonywania dodawania, odejmowania i mnożenia na dużych liczbach całkowitych.

Co to jest RNS

RNS jest jednym z wielu sposobów, które ludzie opracowali w celu identyfikacji liczb całkowitych. W tym systemie liczby są reprezentowane przez sekwencję reszt (które są wynikami po operacji modułu (tj. Resztą po podzieleniu liczb całkowitych)). W tym systemie każda liczba całkowita ma wiele reprezentacji. Aby uprościć sprawę, ograniczymy to tak, aby każda liczba całkowita była reprezentowana w unikalny sposób. Myślę, że łatwiej jest opisać, co się dzieje z konkretnym przykładem.

Spójrzmy na pierwsze trzy liczby pierwsze: 2, 3, 5. W systemie RNS możemy użyć tych trzech liczb, aby jednoznacznie reprezentować dowolną liczbę, która jest mniejsza niż 2 * 3 * 5 = 30, używając reszt. Weź 21:

21 jest mniejsze niż 30, więc możemy to przedstawić za pomocą wyników po modowaniu przez 2, 3 i 5. (tj. Reszta po podzieleniu przez 2, 3 i 5 liczb całkowitych)

Identyfikowalibyśmy 21 za pomocą następującej sekwencji liczb całkowitych:

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

I tak w naszym systemie RNS zamiast „21” użylibyśmy {1,0,1}.

Ogólnie biorąc, biorąc pod uwagę liczbę całkowitą n , reprezentujemy n jako { n mod 2, ..., n mod p_k }, gdzie p_k jest najmniejszą liczbą pierwszą taką, że n jest mniejszy niż iloczyn wszystkich liczb pierwszych mniejszych lub równych p_k .

Kolejny przykład, powiedzmy, że mamy 3412. Musimy użyć tutaj 2,3,5,7,11,13, ponieważ 2*3*5*7*11*13=30030natomiast, 2*3*5*7*11=2310który jest zbyt mały.

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

Zauważasz, że za pomocą tego systemu możemy stosunkowo bezboleśnie reprezentować bardzo duże liczby. Używając reszt {1, 2, 3, 4, 5, 6, 7, 8, ...}, możemy reprezentować liczby do {2, 6, 30, 210, 2310, 30030, 510510, 9699690 ...} odpowiednio. ( Oto seria )

Nasze zadanie

Będziemy używać tych reszt do wykonywania +, - i * na dużych liczbach. Opiszę te procesy poniżej. Na razie tutaj są dane wejściowe i wyjściowe.

Wkład

Otrzymasz dwie (potencjalnie bardzo duże) liczby za pomocą argumentu stdin lub funkcji. Zostaną podane jako ciągi znaków o podstawie 10 cyfr.

W celu dalszego zarysowania problemu nazywamy pierwsze wejście ni drugie m. Załóżmy, że n> m> = 0 .

Będziesz także mieć +albo -albo *wskazać operację wykonać.

Wydajność

Niech x będzie liczbą całkowitą. Użyjemy [ x ] w odniesieniu do reprezentacji RNS opisanej powyżej x .

Masz do wyjścia [n] <operator> [m] = [result]

Jak wykonywać operacje w RNS

Te operacje są stosunkowo proste. Biorąc pod uwagę dwie liczby w notacji RNS, aby je dodać, odjąć lub pomnożyć, po prostu wykonaj podane operacje komponentowo, a następnie weź moduł.

to znaczy

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

Należy zauważyć, że jeśli liczba reszt użytych do przedstawienia dwóch różnych liczb nie jest taka sama, podczas wykonywania operacji konieczne będzie rozszerzenie „krótszej” liczby, aby zawierała tę samą liczbę reszt. Jest to zgodne z tym samym procesem. Zobacz przykłady testowe.

To samo dotyczy sytuacji, gdy wynik wymaga więcej reszt niż którekolwiek wejście. Następnie oba wejścia należy „rozszerzyć”.

Ważne szczegóły

• Będziemy tu zajmować się dużymi liczbami, ale nie arbitralnie dużymi. Będziemy odpowiedzialni za liczby do iloczynu pierwszych 100 liczb pierwszych (patrz poniżej). W tym celu otrzymasz pierwsze 100 liczb pierwszych za darmo (bez kosztów bajtów) . Możesz umieścić je w tablicy o nazwie plub coś idiomatycznego w swoim języku, a następnie odjąć liczbę bajtów użytych do zainicjowania tej tablicy od ostatecznej sumy. To oczywiście oznacza, że ​​mogą być zakodowane na stałe lub możesz użyć wbudowanego do ich wygenerowania.

• Jeśli z jakiegoś powodu jest to domyślna reprezentacja liczb całkowitych używana w twoim języku. W porządku.

• Nie możesz używać żadnych liczb całkowitych dokładnych, chyba że jest to ustawienie domyślne Twojego języka. Jeśli jest to ustawienie domyślne, nie można go używać do przechowywania liczb całkowitych, które zwykle nie mieszczą się w 64 bitach.

• Dla jasności, każda liczba całkowita będzie zawsze reprezentowana z możliwie najmniejszą liczbą reszt. Dotyczy to zarówno wejścia, jak i wyjścia.

• Myślę, że inne specyfikacje powinny temu zapobiec, ale powinny być zbędne: możesz nie wykonać danej operacji na wejściach, a następnie zmienić wszystko na RNS, a następnie na wyjście. Musisz zmienić dane wejściowe na RNS, a następnie wykonać operacje w celu uzyskania danych wyjściowych.

Przypadki testowe

1. Wkład:

n = 10
m = 4
+

Wydajność:

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

Wyjaśnienie:

Najpierw zmień każdy numer na jego reprezentację RNS, jak opisano powyżej:

10 ~ {0,1,0}a 4 ~ {0,1}. Zauważ, że kiedy chcemy dodać komponenty, to 10ma więcej komponentów niż 4. Dlatego musimy „przedłużyć” krótszy numer. Więc napiszemy krótko 4 ~ {0,1} --> {0,1, 4 mod 5} = {0,1,4}. Teraz kontynuujemy dodawanie, a następnie przyjmujemy moduł.

2. Wkład

n=28
m=18
+

Wydajność:

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

3. Wejście (ja zacieram twarz na klawiaturze)

n=1231725471982371298419823012819231982571923
m=1288488183
*

Dane wyjściowe (podzielone na osobne linie dla czytelności):

[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] 

nwymaga 28 liczb pierwszych. mwymaga 10. n*mwymaga 33.

4. Wkład

n=8709668761379269784034173446876636639594408083936553641753483991897255703964943107588335040121154680170867105541177741204814011615930342030904704147856733048115934632145172739949220591246493529224396454328521288726490
m=1699412683745170450115957274739962577420086093042490863793456500767137147999161679589295549397604032154933975242548831536518655879433595016
-

Wydajność:

[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]

nużywa 100 liczb pierwszych. mużywa 70 liczb pierwszych. n-mużywa 99 liczb pierwszych.

Sprawdziłem je za pomocą ChineseRemwbudowanej implementacji twierdzenia Chinese Remainder na GAP (który w zasadzie pobiera liczby RNS i zmienia je na 10 liczb całkowitych). Wierzę, że mają rację. Jeśli coś wydaje się podejrzane, daj mi znać.

Dla tych, którym zależy, produktem pierwszych 100 liczb pierwszych jest:

471193079990618495316248783476026042202057477340967552018863483961641533584503
422120528925670554468197243910409777715799180438028421831503871944494399049257
9030720635990538452312528339864352999310398481791730017201031090

Liczba ta jest o 1 większa niż maksymalna liczba, którą możemy przedstawić przy użyciu danego systemu (i 100 liczb pierwszych).

Nieco spokrewniony

LUKA

Trochę tła: Przyznam, że kiedy tworzyłem to pytanie, wiele miesięcy temu, nie miałem metody rozwiązania trudnej części tego pytania: ustalenia prawidłowej liczby liczb pierwszych do użycia. Na naszej stronie jest wielu bardzo inteligentnych ludzi i naprawdę spodziewałem się, że ktoś wymyśli sposób, aby to zrobić dość szybko. Ponieważ jednak tak się nie stało, nie byłem nawet pewien, czy naprawdę można rozwiązać ten problem. Musiałem więc poświęcić czas na opracowanie metody. Uważam, że to, co zrobiłem, nie łamie żadnej z zasad tego wyzwania, oczywiście chciałbym, aby to sprawdzono.

Trochę żałuję również wyboru golfa kodowego, ponieważ rozwiązania są nieco bardziej dogłębne niż zwykle pasują do formatu tagu. Powiedziawszy to, aby przestrzegać zasad witryny, na dole tego postu znajduje się wersja „golfa” mojego rozwiązania.

Kod

### 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;

Wyjaśnienie:

Na początek obliczamy wszystkie 100 reszt dla obu wejść. Robimy to za pomocą modulusfunkcji w kodzie. Starałem się zachować ostrożność, abyśmy korzystali z wbudowanej modfunkcji po każdym kroku. To gwarantuje, że nigdy nie będziemy mieć liczby większej niż 540^2, która jest o 1 mniejsza niż 100 pierwsza liczba kwadratowa.

Po zebraniu wszystkich pozostałości możemy ponownie wykonać daną operację i modkażdy wpis. Teraz mamy unikalny oznacznik wyniku, ale musimy określić minimalną liczbę pozycji, których musimy użyć do przedstawienia wyniku i każdego z danych wejściowych.

Ustalenie, ile resztek faktycznie potrzebujemy, jest zdecydowanie najtrudniejszą częścią tego problemu. Aby to ustalić, wykonujemy większość kroków twierdzenia chińskiej reszty (CRT). Jednak oczywiście musimy wprowadzić modyfikacje, aby nie skończyć na zbyt dużych liczbach.

Niech prod(i)będzie sumą pierwszych i-1liczb pierwszych. Na przykład,

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

Niech Xbędzie liczbą całkowitą. To znaczy niech {r_i}będą pozostałościamiX

r_i = X mod p_i

Gdzie p_ijest ith prime. To jest 1<i<=100w naszym przypadku.

Teraz mamy zamiar używać CRT znaleźć sekwencję {u_i}takich, że suma w ciągu iod prod(i) * u_ijest równa X. Zauważ, że każdy z nich u_ijest technicznie pozostałością, jak u_i < p_i. Co więcej, jeśli X < prod(i)tak u_i = 0. Ma to kluczowe znaczenie. Oznacza to, że badając końcowe zera, możemy ustalić, ile reszt r_ifaktycznie musimy reprezentować Xw RNS.

Jeśli chcesz sprawdzić niektóre sekwencje u_i, partial_chinesefunkcja zwraca tę u_isekwencję.

Dzięki zabawie z CRT udało mi się znaleźć rekurencyjną formułę u_iwartości, rozwiązując problem określania, ile reszt potrzebujemy.

Formuła jest następująca:

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

Gdzie SUMjest sumą ciągu j in [1,i)od u_j * prod(i).

Oczywiście prod(i)w niektórych przypadkach nie można go obliczyć, ponieważ jest zbyt duży. W tym celu użyłem phi_ifunkcji. Ta funkcja powraca prod(j) (mod p_i). Jest modna każdym kroku, więc nigdy nie obliczamy niczego, co jest zbyt duże.

Jeśli jesteś ciekawy, skąd pochodzi ta formuła, poleciłbym kilka przykładów CRT, które można znaleźć na stronie wikipedia .

Na koniec, dla każdego wejścia, jak również dla naszego wyniku, obliczamy u_isekwencję, a następnie określamy zera końcowe. Następnie wyrzucamy tyle r_iz końca sekwencji reszt.

Kod „golfowy”, 2621 bajtów

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, nie grał w golfa

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}]

• Funkcja rns[d_,l_]konwertuje liczbę całkowitą base-10 na liczbę całkowitą dRNS o długości l.

• Funkcja plus/ times/ subtractdodaj / pomnóż / odejmij jedną liczbę całkowitą RNS do / od drugiej, obie o tej samej długości.

• Funkcja mag[f_]szacuje przybliżoną wielkość liczby zmiennoprzecinkowej fpod względem dolnej granicy długości jej reprezentacji RNS.

• Funkcja ext[m_,n_,i_]wyszukuje resztę z podziału iloczynu mi Prime[Range@n]według Prime[i].

• Funkcja multi[e_,p_,t_]daje najmniejszy mnożnik mspełniający ten warunekDivisible[m*e+t,p]

• Funkcja appx[d_]przyjmuje pierwsze 6cyfry dziesiętnej liczby całkowitej i podaje jej przybliżoną wartość zmiennoprzecinkową.

Za pomocą powyższych funkcji jesteśmy teraz w stanie rozwiązać trudny problem - określić długość wyniku .

Najpierw muszę wyjaśnić, że określenie liczby całkowitej RNS liczby całkowitej nie jest łatwym zadaniem. W przypadku małych liczb całkowitych możemy je porównać bezpośrednio z iloczynem liczb pierwszych. Ale w przypadku bardzo dużych liczb całkowitych, ponieważ zabrania się obliczania iloczynu liczb pierwszych nieskończenie dokładnych, takie porównanie już nie działa.

Na przykład, biorąc pod uwagę, że produkt o doskonałej 1Do 30ma 3.16*10^46długość około RNS liczb całkowitych 3.16*10^46może ewentualnie być 29albo 30. Funkcja magdaje 29jako punkt odniesienia dla tych liczb całkowitych, pokazując, że zarówno 29i 30są możliwe.

Po poznaniu wielkości, po prostu reprezentujemy liczbę całkowitą według tej wielkości bezpośrednio, mając nadzieję na obliczenie jej prawdziwej długości. Sztuczka polega na tym, aby dodać kilka nowych liczb do pierwotnego numeru i zmodyfikować jego reprezentację RNS, dopóki reprezentacja nie będzie zero.

Na przykład mag[211.]jest 4, a jego 4reprezentacja długości to {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

Dodając pewną liczbę, zwiększamy 211do najmniejszej liczby, która jest podzielna przez 210( 2*3*5*7). I teraz dochodzimy do wniosku, że pierwotna liczba jest większa niż 210, ponieważ 420równa się „około” dwa razy 210. Nietrudno wyobrazić sobie, że jeśli zaczniemy 209, ostateczna liczba to „w przybliżeniu” 210.

Funkcja length[f_,n_]przyjmuje wartość zmiennoprzecinkową fdo oszacowania wielkości i koryguje ją na podstawie reprezentacji 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]]]]

Funkcja rnsOperation[a_,b_,op_,rnsop_]daje rnsop[a,b]i opodpowiada normalnym operacjom stosowanym do uzyskania przybliżonych wyników na podstawie wartości zmiennoprzecinkowych.

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]]]

Przykład

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 bajtów

Wyzwanie to znajdowało się na mojej liście życzeń od niedawna, ale dopiero niedawno: a) poświęciłem czas i uwagę na próbę odpowiedzi; i b) faktycznie przetestowałem mój pomysł, aby obliczyć rozmiar liczb (a więc liczbę liczb pierwszych przez porównanie ich z rozmiarem liczb pierwotnych) przy użyciu jakiejś bezbożnej kombinacji logarytmów i twierdzenia o chińskiej reszcie. Niestety, praca z logarytmami przy próbie ustalenia liczby liczb pierwszych, która, na przykład, large_primorial + 3wymaga, oznaczała, że ​​musiałem znaleźć sposoby na obejście problemów zmiennoprzecinkowych.

I to jest port odpowiedzi Liama .

Wypróbuj 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)]))

Wyjaśnienie

Próbując przenieść odpowiedź Liama, osobiście zauważyłem, że niektóre z podanych wyjaśnień były myląco sformułowane, więc oto moja próba wyjaśnienia jego algorytmu.

Najpierw otrzymujemy pozostałości ni m.

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

Obejmuje to przekształcenie wszystkich cyfr ciągów wejściowych i przekształcenie ich w liczby modulo każdej z naszych liczb pierwszych, np. Dla 28, mielibyśmy [(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))

Następnie dodajemy, mnożymy lub odejmujemy reszty parami za pomocą eval()

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

Następnie otrzymujemy rozmiary naszych pozostałości, tj. Minimalną liczbę liczb pierwszych potrzebujemy.

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

Uzyskanie rozmiarów jest najtrudniejszą i najbardziej wymagającą kodu częścią. Używamy partial_chinesefunkcji, która pozwala nam u_iustalić kolejność określania rozmiaru. Więcej u_iza chwilę.

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

Sekwencję u_ioblicza się biorąc każdą resztę r_i, odejmując sumę u_j * primorial(j) for j in [1, i), a następnie dividingprzez primorial(i)wszystkie modulo primes[i]. Oznacza to, że u_i = (r_i - SUM) / primorial(i). Więcej na temat naszych podstawowych funkcji i podziałów za chwilę.

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)oblicza primorial(j) mod primes[i]. Dzielenie modulo dowolny prime pjest łatwo wdrożone przez sprawdzanie multyplikatywnych odwrotności ręcznie, jak możemy być pewni, że wszelkie możliwe u_ijest 0 <= u_i < pzagwarantowane jest względnie pierwsze p i tak ma zagwarantowaną Liczba odwrotna.

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

Po tym wszystkim drukujemy nasz ciąg i gotowe.

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

Co dalej

To było fajne do wdrożenia. Nadal chcę sprawdzić, czy mogę użyć logarytmów w jakiś sposób w innej odpowiedzi. I chciałbym zaimplementować ten kod lub coś w funkcjonalnym języku golfowym, takim jak APL lub Jelly. Wszelkie sugestie i poprawki dotyczące gry w golfa są mile widziane!