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=30030
natomiast, 2*3*5*7*11=2310
któ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 n
i 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
p
lub 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
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 10
ma 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ł.
- Wkład
n=28
m=18
+
Wydajność:
[ 0, 1, 3 ] + [0, 0, 3 ] = [ 0, 1, 1, 4 ]
- 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]
n
wymaga 28 liczb pierwszych. m
wymaga 10. n*m
wymaga 33.
- 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]
n
używa 100 liczb pierwszych. m
używa 70 liczb pierwszych. n-m
używa 99 liczb pierwszych.
Sprawdziłem je za pomocą ChineseRem
wbudowanej 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).
(a,b,o)=>a.map((v,i)=>eval(v+o+b[i]))
na przykład w ES6. Myślę, że najtrudniejszą częścią jest prawdopodobnie znalezienie liczb pierwszych potrzebnych do przedstawienia wyniku bez użycia arytmetyki arbitralnej precyzji, chociaż późniejsza konwersja na RNS nie jest trywialna.1234,1234,+
)?Odpowiedzi:
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
Wyjaśnienie:
Na początek obliczamy wszystkie 100 reszt dla obu wejść. Robimy to za pomocą
modulus
funkcji w kodzie. Starałem się zachować ostrożność, abyśmy korzystali z wbudowanejmod
funkcji 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
mod
każ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ą pierwszychi-1
liczb pierwszych. Na przykład,Niech
X
będzie liczbą całkowitą. To znaczy niech{r_i}
będą pozostałościamiX
Gdzie
p_i
jesti
th prime. To jest1<i<=100
w naszym przypadku.Teraz mamy zamiar używać CRT znaleźć sekwencję
{u_i}
takich, że suma w ciągui
odprod(i) * u_i
jest równaX
. Zauważ, że każdy z nichu_i
jest technicznie pozostałością, jaku_i < p_i
. Co więcej, jeśliX < prod(i)
taku_i = 0
. Ma to kluczowe znaczenie. Oznacza to, że badając końcowe zera, możemy ustalić, ile resztr_i
faktycznie musimy reprezentowaćX
w RNS.Jeśli chcesz sprawdzić niektóre sekwencje
u_i
,partial_chinese
funkcja zwraca tęu_i
sekwencję.Dzięki zabawie z CRT udało mi się znaleźć rekurencyjną formułę
u_i
wartości, rozwiązując problem określania, ile reszt potrzebujemy.Formuła jest następująca:
Gdzie
SUM
jest sumą ciąguj in [1,i)
odu_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łemphi_i
funkcji. Ta funkcja powracaprod(j) (mod p_i)
. Jestmod
na 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_i
sekwencję, a następnie określamy zera końcowe. Następnie wyrzucamy tyler_i
z końca sekwencji reszt.Kod „golfowy”, 2621 bajtów
źródło
Mathematica, nie grał w golfa
Funkcja
rns[d_,l_]
konwertuje liczbę całkowitą base-10 na liczbę całkowitąd
RNS o długościl
.Funkcja
plus
/times
/subtract
dodaj / 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 zmiennoprzecinkowejf
pod względem dolnej granicy długości jej reprezentacji RNS.Funkcja
ext[m_,n_,i_]
wyszukuje resztę z podziału iloczynum
iPrime[Range@n]
wedługPrime[i]
.Funkcja
multi[e_,p_,t_]
daje najmniejszy mnożnikm
spełniający ten warunekDivisible[m*e+t,p]
Funkcja
appx[d_]
przyjmuje pierwsze6
cyfry 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
1
Do30
ma3.16*10^46
długość około RNS liczb całkowitych3.16*10^46
może ewentualnie być29
albo30
. Funkcjamag
daje29
jako punkt odniesienia dla tych liczb całkowitych, pokazując, że zarówno29
i30
są 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.]
jest4
, a jego4
reprezentacja długości to{1, 1, 1, 1}
.Dodając pewną liczbę, zwiększamy
211
do najmniejszej liczby, która jest podzielna przez210
(2*3*5*7
). I teraz dochodzimy do wniosku, że pierwotna liczba jest większa niż210
, ponieważ420
równa się „około” dwa razy210
. Nietrudno wyobrazić sobie, że jeśli zaczniemy209
, ostateczna liczba to „w przybliżeniu”210
.Funkcja
length[f_,n_]
przyjmuje wartość zmiennoprzecinkowąf
do oszacowania wielkości i koryguje ją na podstawie reprezentacji RNSn
.Funkcja
rnsOperation[a_,b_,op_,rnsop_]
dajernsop[a,b]
iop
odpowiada normalnym operacjom stosowanym do uzyskania przybliżonych wyników na podstawie wartości zmiennoprzecinkowych.Przykład
źródło
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 + 3
wymaga, oznaczała, że musiałem znaleźć sposoby na obejście problemów zmiennoprzecinkowych.I to jest port odpowiedzi Liama .
Wypróbuj online!
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
n
im
.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]
Następnie dodajemy, mnożymy lub odejmujemy reszty parami za pomocą
eval()
Następnie otrzymujemy rozmiary naszych pozostałości, tj. Minimalną liczbę liczb pierwszych potrzebujemy.
Uzyskanie rozmiarów jest najtrudniejszą i najbardziej wymagającą kodu częścią. Używamy
partial_chinese
funkcji, która pozwala namu_i
ustalić kolejność określania rozmiaru. Więceju_i
za chwilę.Sekwencję
u_i
oblicza się biorąc każdą resztęr_i
, odejmując sumęu_j * primorial(j) for j in [1, i)
, a następniedividing
przezprimorial(i)
wszystkie moduloprimes[i]
. Oznacza to, żeu_i = (r_i - SUM) / primorial(i)
. Więcej na temat naszych podstawowych funkcji i podziałów za chwilę.phi_i(j, i)
obliczaprimorial(j) mod primes[i]
. Dzielenie modulo dowolny primep
jest łatwo wdrożone przez sprawdzanie multyplikatywnych odwrotności ręcznie, jak możemy być pewni, że wszelkie możliweu_i
jest0 <= u_i < p
zagwarantowane jest względnie pierwsze p i tak ma zagwarantowaną Liczba odwrotna.Po tym wszystkim drukujemy nasz ciąg i gotowe.
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!
źródło