X-Git-Url: https://ginac.de/CLN/cln.git//cln.git?a=blobdiff_plain;f=src%2Fbase%2Fdigitseq%2Fcl_DS_mul.cc;h=774edce762a59850c42190b7834d4c96a1f453e9;hb=665c18cd376d8d8c5a8eafb30681a3f9f46d4a99;hp=76be717f417f849d9118f76efefa61bb37ba19c9;hpb=c486b78a1a0613f07a10816d6f6ca9e485bc8290;p=cln.git diff --git a/src/base/digitseq/cl_DS_mul.cc b/src/base/digitseq/cl_DS_mul.cc index 76be717..774edce 100644 --- a/src/base/digitseq/cl_DS_mul.cc +++ b/src/base/digitseq/cl_DS_mul.cc @@ -21,7 +21,7 @@ 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); @@ -38,12 +38,12 @@ namespace cln { 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); }); } @@ -170,7 +170,7 @@ namespace cln { // 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.) @@ -184,7 +184,7 @@ namespace cln { // 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.) @@ -197,9 +197,9 @@ namespace cln { 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.) @@ -213,10 +213,10 @@ namespace cln { 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: @@ -299,7 +299,7 @@ namespace cln { // // 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 @@ -354,28 +354,28 @@ namespace cln { 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 (uintC len1, uintC 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) { const unsigned int prod_threshold = cl_fftm_threshold*(cl_fftm_threshold-cl_fftm_threshold1); if (len1-cl_fftm_threshold1 >= prod_threshold) - return cl_true; + return true; if (len2-cl_fftm_threshold1 >= prod_threshold) - return cl_true; + return true; var uint32 hi; var uint32 lo; mulu32(len1-cl_fftm_threshold1,len2-cl_fftm_threshold1, hi=,lo=); if (hi > 0 || lo >= prod_threshold) - return cl_true; + 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 @@ -401,7 +401,7 @@ namespace cln { // 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 @@ -442,9 +442,9 @@ namespace cln { #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 @@ -482,7 +482,7 @@ namespace cln { 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