In meiner Freizeit bereite ich mich auf Interviewfragen vor wie: implementiere multiplizierende Zahlen, die als Zahlenfelder dargestellt werden . Offensichtlich bin ich gezwungen, es von Grund auf in einer Sprache wie Python oder Java zu schreiben, daher ist eine Antwort wie "GMP verwenden" nicht akzeptabel (wie hier erwähnt: Verständnis Schönhage-Straßen-Algorithmus (riesige Ganzzahl Multiplikation) ).
Für welche genau range der Größen dieser 2 Zahlen (d. h. Anzahl der Ziffern), sollte ich
Ist Schönhage-Strassen O(n log n log log n) immer eine gute Lösung? Wikipedia erwähnt, dass Schönhage-Strassen für Zahlen jenseits von 2^2^15 bis 2^2^17 ratsam ist. Was tun, wenn eine Zahl lächerlich groß ist (z. B. 10,000 bis 40,000 Dezimalziffern), aber die zweite besteht aus nur ein paar Ziffern?
Parallelisieren all diese 4 Algorithmen leicht?
Sie können die Quelle der GNU Multiple Precision Arithmetic Library durchsuchen und ihre Schwellenwerte für Wechsel zwischen Algorithmen .
Pragmatischer sollten Sie nur Ihre Implementierung der Algorithmen profilieren. GMP setzt viel Aufwand in die Optimierung, so dass ihre Algorithmen andere konstante Faktoren haben als Ihre. Der Unterschied könnte die Schwellenwerte leicht um eine Größenordnung verschieben. Finden Sie heraus, wo sich die Zeiten kreuzen, wenn die Eingabegröße für Ihren Code zunimmt, und legen Sie die Schwellenwerte entsprechend fest.
Ich denke, dass alle Algorithmen parallelisiert werden können, da sie hauptsächlich aus Pässen bestehen. Aber bedenken Sie, dass Parallelisierung eine andere Sache ist, die die Schwellenwerte ziemlich viel bewegen wird.
Tags und Links algorithm