#include "cl_low.h"
#include "cln/malloc.h"
-#include "cln/abort.h"
+#include "cln/exception.h"
namespace cln {
// multipliziert die UDS sourceptr1[-len1..-1] (len1>0)
// mit der UDS sourceptr2[-len1..-1] (len2>0)
// und legt das Ergebnis in der UDS destptr[-len..-1] (len=len1+len2) ab.
-// Unterhalb von destptr werden len Digits Platz benötigt.
+// Unterhalb von destptr werden len Digits Platz benötigt.
void cl_UDS_mul (const uintD* sourceptr1, uintC len1,
const uintD* sourceptr2, uintC len2,
uintD* destptr);
mulu_loop_lsp(lsprefnext(sourceptr1),sourceptr2,destptr,len2);
lsshrink(destptr);
var uintD* destptr2 = destptr lspop len2;
- // äußere Schleife läuft über source1 :
+ // äußere Schleife läuft über source1 :
dotimespC(len1,len1-1,
- { // innere Schleife läuft über source2 :
+ { // innere Schleife läuft über source2 :
var uintD carry =
muluadd_loop_lsp(lsprefnext(sourceptr1),sourceptr2,destptr,len2);
- lsprefnext(destptr2) = carry; // UDS um das Carry-Digit verlängern
+ lsprefnext(destptr2) = carry; // UDS um das Carry-Digit verlängern
lsshrink(destptr);
});
}
// FFT-Multiplikation nach Nussbaumer: O(n log n log log n)
#include "cl_DS_mul_nuss.h"
- // nuss_threshold = Länge, ab der die Nussbaumer-Multiplikation bevorzugt
+ // nuss_threshold = Länge, ab der die Nussbaumer-Multiplikation bevorzugt
// wird. Der Break-Even-Point bestimmt sich aus Zeitmessungen.
// Multiplikation zweier N-Wort-Zahlen unter Linux mit einem 80486:
// N kara nuss nuss-asm (time in sec.)
// FFT-Multiplikation in Z/pZ: O(n log n log log n)
#include "cl_DS_mul_fftp.h"
- // fftp_threshold = Länge, ab der die FFT-Multiplikation mod p bevorzugt
+ // fftp_threshold = Länge, ab der die FFT-Multiplikation mod p bevorzugt
// wird. Der Break-Even-Point bestimmt sich aus Zeitmessungen.
// Multiplikation zweier N-Wort-Zahlen unter Linux mit einem 80486:
// N kara fftp (time in sec.)
int cl_fftp_threshold = 1000000;
// FFT-Multiplikation in Z/pZ: O(n log n log log n)
-// für drei verschiedene Primzahlen p1,p2,p3 < 2^32.
+// für drei verschiedene Primzahlen p1,p2,p3 < 2^32.
#include "cl_DS_mul_fftp3.h"
- // fftp3_threshold = Länge, ab der die FFT-Multiplikation mod p_i bevorzugt
+ // fftp3_threshold = Länge, ab der die FFT-Multiplikation mod p_i bevorzugt
// wird. Der Break-Even-Point bestimmt sich aus Zeitmessungen.
// Multiplikation zweier N-Wort-Zahlen unter Linux mit einem 80486:
// N kara fftp3 fftp (time in sec.)
int cl_fftp3_threshold = 1000000;
// FFT-Multiplikation in Z/pZ: O(n log n log log n)
-// für drei verschiedene Primzahlen p1,p2,p3 < 2^32,
+// für drei verschiedene Primzahlen p1,p2,p3 < 2^32,
// mit Montgomery-Multiplikation.
#include "cl_DS_mul_fftp3m.h"
- // fftp3_threshold = Länge, ab der die FFT-Multiplikation mod p_i bevorzugt
+ // fftp3_threshold = Länge, ab der die FFT-Multiplikation mod p_i bevorzugt
// wird. Der Break-Even-Point bestimmt sich aus Zeitmessungen.
// Multiplikation zweier N-Wort-Zahlen unter
// Linux mit einem 80486, 33 MHz, mit Benutzung der GMP-Low-Level-Funktionen:
// // 1250 3100 1.35 1.07 0.28 0.21
// // Es gibt also noch Werte von (len1,len2) mit 1250 <= len1 <= len2, bei
// // denen "kara" schneller ist als "fftm", aber nicht viele und dort auch
- // // nur um 5%. Darum wählen wir ab hier die FFT-Multiplikation.
+ // // nur um 5%. Darum wählen wir ab hier die FFT-Multiplikation.
// // 140000: 4.15s 12.53 23.7
// // 14000: 4.16s
// // 11000: 4.16s
const unsigned int cl_fftm_threshold2 = 2*cl_fftm_threshold;
// len1 > cl_fftm_threshold1 && len2 > cl_fftm_threshold2
// && len1 >= cl_fftm_threshold1 + cl_fftm_threshold/(len2-cl_fftm_threshold1)*(cl_fftm_threshold-cl_fftm_threshold1).
- static inline cl_boolean cl_fftm_suitable (uintL len1, uintL len2)
+ static inline bool cl_fftm_suitable (uintC len1, uintC len2)
{ if (len1 >= cl_fftm_threshold)
- return cl_true;
+ return true;
if (len1 > cl_fftm_threshold1)
if (len2 > cl_fftm_threshold2)
- { var uint32 hi;
+ { const unsigned int prod_threshold = cl_fftm_threshold*(cl_fftm_threshold-cl_fftm_threshold1);
+ if (len1-cl_fftm_threshold1 >= prod_threshold)
+ return true;
+ if (len2-cl_fftm_threshold1 >= prod_threshold)
+ return true;
+ var uint32 hi;
var uint32 lo;
mulu32(len1-cl_fftm_threshold1,len2-cl_fftm_threshold1, hi=,lo=);
- if (hi > 0 || lo >= cl_fftm_threshold*(cl_fftm_threshold-cl_fftm_threshold1))
- return cl_true;
+ if (hi > 0 || lo >= prod_threshold)
+ return true;
}
- return cl_false;
+ return false;
}
#if 0 // Doesn't seem to be worth the effort
-// FFT-Multiplikation über den komplexen Zahlen.
+// FFT-Multiplikation über den komplexen Zahlen.
#include "cl_DS_mul_fftc.h"
// Multiplikation zweier N-Wort-Zahlen unter
// Linux mit einem i486 33 MHz
// 10000 0.88 4.95
// 25000 2.3 (15MB)
-// FFT-Multiplikation über den komplexen Zahlen, Symmetrie ausnutzend.
+// FFT-Multiplikation über den komplexen Zahlen, Symmetrie ausnutzend.
#include "cl_DS_mul_fftcs.h"
// Multiplikation zweier N-Wort-Zahlen unter
// Linux mit einem i486 33 MHz
#endif
-#if 0 // Keine gute Fehlerabschätzung
+#if 0 // Keine gute Fehlerabschätzung
-// FFT-Multiplikation über den komplexen Zahlen, mit reellen Zahlen rechnend.
+// FFT-Multiplikation über den komplexen Zahlen, mit reellen Zahlen rechnend.
#include "cl_DS_mul_fftr.h"
// Multiplikation zweier N-Wort-Zahlen unter
// Linux mit einem i486 33 MHz
if (len1 < cl_karatsuba_threshold)
// Multiplikation nach Schulmethode
mulu_2loop(sourceptr1,len1,sourceptr2,len2,destptr);
- else // len1 groß
+ else // len1 groß
if (!cl_fftm_suitable(len1,len2))
// Karatsuba-Multiplikation
// (ausgelagert, um die eigentliche Multiplikationsfunktion nicht
var uintD tmpprod_xxx = cl_alloc_array(uintD,len1+len2);
mulu_xxx(sourceptr1,len1,sourceptr2,len2,arrayLSDptr(tmpprod_xxx,len1+len2));
if (compare_loop_msp(destptr lspop (len1+len2),arrayMSDptr(tmpprod_xxx,len1+len2),len1+len2))
- cl_abort();
+ throw runtime_exception();
}
#endif
}
git://www.ginac.de / cln.git / blobdiff