Ergebnis der Suchanfrage

• Forum: Programmieren allgemein

  Re: FFT für schnelle Multiplikation

   
    by negaH, 28. Feb 2007
  Hm, entweder mache ich jetzt einen fatalen Denkfehler oder du ;)
  
  Die Zahl 2^(2^27)-1 benötigt exakt 2^27 Bits im Speicher und Ln2(2^2^27) ist nach meinem Wissen 2^27. Die Multiplikation von 2 Zahlen mit 2^27 Bits jeweils ergibt also ein Resulat mit 2^(27*2) Bits.
  
  Ln2(A) + Ln2(B) = Ln2(Resulat) ->
  Result := A * B;
  
  Ln2(A) = Anzahl Bits die die Zahl A benötigt.
  
  Ich weiß nicht, aber ich...
• Forum: Programmieren allgemein

  Re: FFT für schnelle Multiplikation

   
    by negaH, 27. Feb 2007
  Stop ;) du implementierst da den falschen Algortihmus. In der Zahlentheorie bzw. den dazu nötigen Bibliotheken wird der
  
  modulare Fermat Schönhage Strassen
  
  benutzt. Dieser arbeitet nicht mit komplexen Zahlen sondern modular zu Fermat'schen Zahlen -> die sind praktisch gesehen vergleichbar mit Primzahlen (aus Sicht ihrer Eigenschaften für diese FFT)
  
  Je nach Implementierung benötigt man...