In Anbetracht der zahlreichen Herausforderungen hielt ich dies für interessant.
In dieser Herausforderung werden wir das Residue Number System (RNS) verwenden, um Additionen, Subtraktionen und Multiplikationen mit großen ganzen Zahlen durchzuführen.
Was ist der RNS
Das RNS ist eine von vielen Möglichkeiten, die Menschen entwickelt haben, um Ganzzahlen zu identifizieren. In diesem System werden Zahlen durch eine Folge von Resten dargestellt (die die Ergebnisse nach einer Moduloperation sind (dh der Rest nach der Ganzzahldivision)). In diesem System hat jede Ganzzahl viele Darstellungen. Um die Dinge einfach zu halten, werden wir die Dinge so einschränken, dass jede ganze Zahl eindeutig dargestellt wird. Ich denke, es ist einfacher, mit einem konkreten Beispiel zu beschreiben, was passiert.
Schauen wir uns die ersten drei Primzahlen an: 2, 3, 5. Im RNS-System können wir diese drei Zahlen verwenden, um mit Resten eindeutig jede Zahl darzustellen, die kleiner als 2 * 3 * 5 = 30 ist. Nimm 21:
21 ist kleiner als 30, daher können wir es mit den Ergebnissen nach der Modifikation durch 2, 3 und 5 darstellen. (Dh der Rest nach der Ganzzahldivision durch 2, 3 und 5)
Wir würden 21 mit der folgenden Folge von ganzen Zahlen identifizieren:
21 ~ {21 mod 2, 21 mod 3, 21 mod 5} = {1, 0, 1}
Und so würden wir in unserem RNS-System anstelle von "21" {1,0,1} verwenden.
Im Allgemeinen stellen wir n mit einer ganzen Zahl n als { n mod 2, ..., n mod p_k } dar, wobei p_k die kleinste Primzahl ist, sodass n kleiner als das Produkt aller Primzahlen ist, die kleiner oder gleich p_k sind .
Ein anderes Beispiel, sagen wir, wir haben 3412. Wir müssen hier 2,3,5,7,11,13 verwenden, weil 2*3*5*7*11*13=30030
wohingegen, 2*3*5*7*11=2310
was zu klein ist.
3412 ~ {3412 mod 2, 3412 mod 3, 3412, mod 5, ..., 3412 mod 13} = {0, 1, 2, 3, 2, 6}
Sie bemerken, dass wir mit diesem System relativ schmerzlos sehr große Zahlen darstellen können. Mit {1, 2, 3, 4, 5, 6, 7, 8, ...} Resten können wir Zahlen bis zu {2, 6, 30, 210, 2310, 30030, 510510, 9699690 ...} darstellen. beziehungsweise. ( Hier ist die Serie )
Unsere Aufgabe
Wir werden diese Reste verwenden, um +, - und * für große Zahlen durchzuführen. Ich werde diese Prozesse im Folgenden beschreiben. Vorerst sind hier die Eingangs- und Ausgangsspezifikationen.
Eingang
Sie erhalten zwei (möglicherweise sehr große) Zahlen über ein Standard- oder Funktionsargument. Sie werden als Zeichenfolgen mit 10 Stellen zur Basis angegeben.
Um das Problem weiter zu skizzieren, bezeichnen wir die erste Eingabe n
als die zweite m
. Angenommen, n> m> = 0 .
Sie erhalten auch +
oder -
oder *
, um die auszuführende Operation anzugeben.
Ausgabe
Sei x eine ganze Zahl. Wir werden mit [ x ] auf die oben beschriebene RNS-Darstellung von x verweisen .
Sie sollen ausgeben [n] <operator> [m] = [result]
So führen Sie die Vorgänge in RNS durch
Diese Operationen sind relativ einfach. Wenn Sie zwei Zahlen in der RNS-Notation angeben, um sie zu addieren, zu subtrahieren oder zu multiplizieren, führen Sie einfach die angegebenen Operationen komponentenweise aus und nehmen Sie dann den Modul.
dh
{1, 2, 3} + {1, 1, 4} = {(1 + 1) mod 2, (2 + 1) mod 3, (3 + 4) mod 5} = {0, 0, 2}
Beachten Sie, dass Sie bei der Ausführung von Vorgängen die "kürzere" Anzahl so verlängern müssen, dass sie dieselbe Anzahl von Resten enthält, wenn die Anzahl von Resten, die zur Darstellung von zwei verschiedenen Nummern verwendet wird, nicht identisch ist. Dies folgt dem gleichen Vorgang. Ein Beispiel finden Sie in den Testfällen.
Gleiches gilt, wenn das Ergebnis mehr Rückstände erfordert als jede Eingabe. Dann müssen beide Eingänge "erweitert" werden.
Wichtige Details
Wir werden es hier mit großen Zahlen zu tun haben, aber nicht mit willkürlich großen. Wir sind für Zahlen bis zum Produkt der ersten 100 Primzahlen verantwortlich (siehe unten). Zu diesem Zweck erhalten Sie die ersten 100 Primzahlen kostenlos (keine Bytekosten) . Sie können sie in ein Array mit dem Namen
p
oder etwas Idiomatisches für Ihre Sprache einfügen und dann die Anzahl der Bytes, die zum Einleiten dieses Arrays verwendet wurden, von Ihrer endgültigen Summe abziehen. Dies bedeutet natürlich, dass sie fest codiert sein können oder dass Sie ein eingebautes verwenden können, um sie zu generieren.Wenn dies aus irgendeinem Grund die in Ihrer Sprache verwendete Standard-Ganzzahldarstellung ist. Das ist gut.
Sie dürfen keinen Arbitrary Precision Integer-Typ verwenden, es sei denn, dies ist die Standardeinstellung Ihrer Sprache. Wenn dies die Standardeinstellung ist, können Sie sie möglicherweise nicht zum Speichern von Ganzzahlen verwenden, die normalerweise nicht in 64 Bit passen.
Es ist klar, dass jede Ganzzahl immer mit den geringstmöglichen Resten dargestellt wird. Dies gilt sowohl für die Eingabe als auch für die Ausgabe.
Ich denke, die anderen Spezifikationen sollten dies verhindern, aber redundant sein: Sie können die angegebene Operation nicht an den Eingängen ausführen und dann und dann alles in RNS ändern und dann ausgeben. Sie müssen die Eingaben in RNS ändern und dann die Vorgänge ausführen, um die Ausgabe zu erzeugen.
Testfälle
Eingang:
n = 10
m = 4
+
Ausgabe:
{ 0, 1, 0 } + { 0, 1 } = { 0, 2, 4 }
Erläuterung:
Ändern Sie zunächst jede Zahl in ihre RNS-Darstellung, wie oben beschrieben:
10 ~ {0,1,0}
und 4 ~ {0,1}
. Beachten Sie, dass, wenn Sie komponentenweise hinzufügen möchten, dies 10
mehr Komponenten als enthält 4
. Deshalb müssen wir die kürzere Zahl "verlängern". Also werden wir kurz schreiben 4 ~ {0,1} --> {0,1, 4 mod 5} = {0,1,4}
. Nun fahren wir mit der Addition fort und nehmen dann den Modul.
- Eingang
n=28
m=18
+
Ausgabe:
[ 0, 1, 3 ] + [0, 0, 3 ] = [ 0, 1, 1, 4 ]
- Eingabe (ich zerdrücke mein Gesicht auf der Tastatur)
n=1231725471982371298419823012819231982571923
m=1288488183
*
Ausgabe (zur besseren Lesbarkeit in separate Zeilen unterteilt):
[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
benötigt 28 Primzahlen. m
benötigt 10. n*m
benötigt 33.
- Eingang
n=8709668761379269784034173446876636639594408083936553641753483991897255703964943107588335040121154680170867105541177741204814011615930342030904704147856733048115934632145172739949220591246493529224396454328521288726490
m=1699412683745170450115957274739962577420086093042490863793456500767137147999161679589295549397604032154933975242548831536518655879433595016
-
Ausgabe:
[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
verwendet 100 Primzahlen. m
verwendet 70 Primzahlen. n-m
verwendet 99 Primzahlen.
Ich habe diese anhand der ChineseRem
integrierten Implementierung des chinesischen Resttheorems für GAP überprüft (das im Grunde genommen RNS-Zahlen verwendet und sie in Basis-10-Ganzzahlen ändert). Ich glaube, dass sie richtig sind. Wenn etwas faul zu sein scheint, lassen Sie es mich bitte wissen.
Für die, die sich interessieren, ist das Produkt der ersten 100 Primzahlen:
471193079990618495316248783476026042202057477340967552018863483961641533584503
422120528925670554468197243910409777715799180438028421831503871944494399049257
9030720635990538452312528339864352999310398481791730017201031090
Diese Zahl ist um 1 größer als die maximale Zahl, die wir mit dem angegebenen System darstellen können (und die Beschränkung auf 100 Primzahlen).
(a,b,o)=>a.map((v,i)=>eval(v+o+b[i]))
in ES6 ausgeführt. Ich denke, der schwierigste Teil ist es wahrscheinlich, die Anzahl der Primzahlen zu finden, die zur Darstellung des Ergebnisses benötigt werden, ohne eine Arithmetik mit willkürlicher Genauigkeit zu verwenden, obwohl die anschließende Konvertierung in RNS nicht gerade trivial ist.1234,1234,+
)?Antworten:
SPALT
Hintergrund: Ich gebe zu, als ich diese Frage vor so vielen Monaten erstellt habe, hatte ich keine Methode, um den schwierigen Teil dieser Frage zu lösen: die richtige Anzahl der zu verwendenden Primzahlen zu bestimmen. Wir haben eine Menge sehr intelligenter Leute auf dieser Seite, und ich hatte wirklich erwartet, dass jemand einen Weg finden würde, dies ziemlich schnell zu tun. Da dies jedoch nicht geschah, war ich mir nicht einmal sicher, ob es wirklich möglich war, dieses Problem zu lösen. Also musste ich mir die Zeit nehmen, um eine Methode zu entwickeln. Ich glaube, dass das, was ich getan habe, nicht gegen die Regeln dieser Herausforderung verstößt. Natürlich würde ich es begrüßen, wenn dies überprüft würde.
Ich bedaure auch die Wahl von Code-Golf ein wenig, weil die Lösungen etwas ausführlicher sind, als es normalerweise für das Tag-Format passt. Um die Site-Regeln zu befolgen, finden Sie unten in diesem Beitrag eine "Golf" -Version meiner Lösung.
Code
Erläuterung:
Zu Beginn berechnen wir alle 100 der Rückstände für beide Eingänge. Wir machen das mit der
modulus
Funktion im Code. Ich habe versucht, vorsichtig zu sein, damit wir die eingebautemod
Funktion nach jedem Schritt verwenden. Dies stellt sicher, dass wir niemals eine Zahl haben, die größer als540^2
, also 1 kleiner als das 100. Quadratzoll ist.Nachdem wir alle Reste haben, können wir die angegebene Operation und
mod
jeden Eintrag erneut ausführen . Jetzt haben wir einen eindeutigen Bezeichner für das Ergebnis, aber wir müssen die minimale Anzahl von Einträgen bestimmen, die wir verwenden müssen, um das Ergebnis und jede der Eingaben darzustellen.Herauszufinden, wie viele Rückstände wir tatsächlich benötigen, ist der mit Abstand schwierigste Teil dieses Problems. Um dies festzustellen, führen wir die meisten Schritte des Chinese Remainder Theorem (CRT) aus. Wir müssen natürlich Änderungen vornehmen, damit wir nicht zu große Zahlen erhalten.
Sei
prod(i)
die Summe der ersteni-1
Primzahlen. Beispielsweise,Sei
X
eine ganze Zahl. Lassen Sie{r_i}
die Reste seinX
, das heißtWo
p_i
ist deri
th prime. Dies ist für1<i<=100
in unserem Fall.Jetzt werden wir die CRT verwenden, um eine Sequenz zu finden
{u_i}
, bei der die Summei
vonprod(i) * u_i
gleich istX
. Beachten Sie, dass jedesu_i
auch technisch ein Rückstand ist, wieu_i < p_i
. Außerdem, wennX < prod(i)
dannu_i = 0
. Dies ist von entscheidender Bedeutung. Dies bedeutet, dass wir durch Untersuchen der nachfolgenden Nullen bestimmen können, wie viele der Rester_i
wir tatsächlichX
im RNS darstellen müssen.Wenn Sie einige Sequenzen von untersuchen möchten
u_i
, gibt diepartial_chinese
Funktion dieu_i
Sequenz zurück.Indem ich mit der CRT herumgespielt habe, konnte ich eine rekursive Formel für die
u_i
Werte finden und das Problem lösen, wie viele Rückstände wir benötigen.Die Formel lautet:
Wo
SUM
ist die Summej in [1,i)
vonu_j * prod(i)
.Natürlich
prod(i)
kann in manchen Fällen nicht wirklich gerechnet werden, weil es zu groß ist. Zu diesem Zweck habe ich diephi_i
Funktion verwendet. Diese Funktion kehrt zurückprod(j) (mod p_i)
. Es istmod
bei jedem Schritt so, dass wir nie etwas berechnen, das zu groß ist.Wenn Sie neugierig sind, woher diese Formel stammt, empfehle ich Ihnen, einige Beispiele für CRTs zu verwenden, die auf der Wikipedia-Seite zu finden sind .
Schließlich berechnen wir für jede Eingabe sowie für unsere Ausgabe die
u_i
Sequenz und bestimmen dann die nachfolgenden Nullen. Dann werfen wir so vieler_i
aus dem Ende der Restsequenzen heraus."Golfed" Code, 2621 Bytes
quelle
Mathematica, nicht golfen
Die Funktion
rns[d_,l_]
konvertiert eine Ganzzahld
zur Basis 10 in eine RNS-Ganzzahl der Längel
.Funktion
plus
/times
/subtract
addiere / multipliziere / subtrahiere eine RNS-Ganzzahl von / zu einer anderen, die beide die gleiche Länge haben.Die Funktion
mag[f_]
schätzt die ungefähre Größe der Gleitkommazahlf
in Bezug auf die Untergrenze der Länge ihrer RNS-Darstellung.Die Funktion ermittelt
ext[m_,n_,i_]
den Rest aus der Aufteilung des Produkts vonm
undPrime[Range@n]
nachPrime[i]
.Die Funktion
multi[e_,p_,t_]
gibt den kleinsten Multiplikator, der diesm
erfülltDivisible[m*e+t,p]
Die Funktion
appx[d_]
nimmt die ersten6
Stellen einer Dezimalzahl und gibt den ungefähren Gleitkommawert an.Mit Hilfe der obigen Funktionen können wir nun ein kniffliges Problem lösen - die Länge des Ergebnisses bestimmen .
Zunächst muss klargestellt werden, dass es keine leichte Aufgabe ist, die RNS-Länge einer Ganzzahl zu bestimmen. Für kleine ganze Zahlen können wir sie direkt mit dem Produkt von Primzahlen vergleichen. Da es für sehr große ganze Zahlen verboten ist, das Produkt von Primzahlen unendlich genau zu berechnen, funktioniert ein solcher Vergleich nicht mehr.
Wenn beispielsweise das Produkt von prime
1
to30
ist3.16*10^46
, kann die RNS-Länge von ganzen Zahlen3.16*10^46
möglicherweise29
oder sein30
. Die Funktionmag
gibt29
für diese ganzen Zahlen als Referenz, die zeigen , dass beide29
und30
möglich sind.Sobald wir die Größe kennen, stellen wir einfach die ganze Zahl direkt entsprechend dieser Größe dar, in der Hoffnung, ihre wahre Länge zu berechnen. Der Trick dabei ist, der ursprünglichen Nummer einige neue Nummern hinzuzufügen und ihre RNS-Darstellung zu ändern, bis die Darstellung vollständig Null ist.
Zum Beispiel
mag[211.]
ist4
, und seine Längendarstellung4
ist{1, 1, 1, 1}
.Indem wir eine Zahl hinzufügen, erhöhen wir uns
211
auf die kleinste Zahl, die durch210
(2*3*5*7
) teilbar ist . Und jetzt kommen wir zu dem Schluss, dass die ursprüngliche Zahl größer ist als210
, da420
"ungefähr" das Zweifache von210
. Es ist nicht schwer vorstellbar, dass209
die endgültige Zahl "ungefähr" ist , wenn wir von hier ausgehen210
.Die Funktion verwendet
length[f_,n_]
den Gleitkommawertf
zum Schätzen der Größe und korrigiert ihn auf der Grundlage seiner RNS-Darstellungn
.Die Funktion
rnsOperation[a_,b_,op_,rnsop_]
liefertrnsop[a,b]
undop
gibt die entsprechenden normalen Operationen an, die verwendet werden, um ungefähre Ergebnisse basierend auf Gleitkommawerten zu erhalten.Beispiel
quelle
Python 3 , 435 Bytes
Diese Herausforderung steht schon seit einiger Zeit auf meiner Bucket-Liste, aber erst seit kurzem gilt Folgendes: a) Ich habe Zeit und Aufmerksamkeit darauf verwendet, tatsächlich eine Antwort zu versuchen. und b) tatsächlich meine Idee getestet, die Größe der Zahlen (und damit die Anzahl der Primzahlen durch Vergleichen mit der Größe der Primzahlen) unter Verwendung einer unheiligen Kombination von Logarithmen und dem chinesischen Restsatz zu berechnen. Leider bedeutete die Arbeit mit Logarithmen, während versucht wurde, die Anzahl der
large_primorial + 3
erforderlichen Primzahlen zu bestimmen , dass ich nach Wegen suchen musste, um Gleitkommaprobleme zu umgehen.Und so ist dies eine Portierung von Liams Antwort .
Probieren Sie es online!
Erläuterung
Beim Versuch, Liams Antwort zu portieren, stellte ich persönlich fest, dass einige der gegebenen Erklärungen verwirrend formuliert waren. Dies ist also mein Versuch, seinen Algorithmus zu erklären.
Zunächst erhalten wir die Rückstände von
n
undm
.Dabei werden alle Ziffern der Eingabezeichenfolgen in Zahlen umgewandelt, die für jede unserer Primzahlen modulo sind, z. B. für 28, die wir haben würden
[(20 + 8) mod 2, (20 + 8) mod 3, (20 + 8) mod 5, etc]
Dann addieren, multiplizieren oder subtrahieren wir die Reste paarweise mit
eval()
Dann erhalten wir die Größe unserer Reste, dh die minimale Anzahl von Primzahlen, die wir benötigen.
Das Erhalten der Größen ist der schwierigste und codeintensivste Teil. Wir benutzen die
partial_chinese
Funktion, mit der wir unsere Reihenfolgeu_i
bestimmen können. Mehr überu_i
in einem Augenblick.Die Sequenz
u_i
wird bestimmt , indem jeder Rest berechnetr_i
, Subtrahieren der Summeu_j * primorial(j) for j in [1, i)
, und danndividing
durchprimorial(i)
, die alle moduloprimes[i]
. Das heißt,u_i = (r_i - SUM) / primorial(i)
. Mehr über unsere Ur- und Teilungsfunktionen in einem Moment.phi_i(j, i)
berechnetprimorial(j) mod primes[i]
. Division modulo jeder Primzahlp
leicht durch Überprüfung für multiplikativen Umkehrungen manuell implementiert ist, wie wir sicher sein können , dass eine möglicheu_i
ist0 <= u_i < p
garantiert coprime p zu sein , und so ist eine multiplikative Inverse garantiert.Nach alledem drucken wir unseren String und wir sind fertig.
Was kommt als nächstes
Die Implementierung hat Spaß gemacht. Ich möchte immer noch sehen, ob ich Logarithmen in einer anderen Antwort verwenden kann. Und ich möchte diesen Code oder so etwas in eine funktionierende Golfsprache wie APL oder Jelly implementieren. Alle Vorschläge und Korrekturen zum Golfen sind willkommen!
quelle