4. Algorithmus für Modulo

Algorithmus für Modulo

  • C

    Hallo allerseits!

    Kennt jemand einen Algorithmus der (schnell) das Modulo zweier Zahlen errechnet?

    0
  • B

    wenn er allgemein gehalten werden soll (d.h. du hast keine Einschraenkungen auf den beiden Operanden, wie "x ist sicher ein Vielfaches von 5" oder so), dann gibts sicher nichts schnelleres als das normale Modulo, wie's in der CPU eingebrandt ist. Wuerds naemlich was schnelleres geben, das fuer alle Zahlen funktioniert, dann wuerde man ziemlich sicher das in die CPUs einbauen 😉

    0
  • V

    ChrisPlusPlus schrieb:

    Hallo allerseits!
    Kennt jemand einen Algorithmus der (schnell) das Modulo zweier Zahlen errechnet?

    fällt beim dividieren eh ab.

    welche sprache, welche typen, was schwebt dir vor?

    in c++ schreibt man für ganzzahltypen bis 64 bit einfach a%b und hat's ergebnis in der hand.

    hier hab ich modulo-code, den ich mal für einen wettbewerb in brainfuck geschrieben habe:

    MOD
    PUSHZERO result >
    DUP1 count <[->>+>+<<<]>>>[-<<<+>>>]<
    DEC count -
    // divisor=5 dividend=2 result=0 (count=2) tmp
    go divisor <<<
    WHILE divisor [
    go count >>>
    DUP0 tmp [->+>+<<]>>[-<<+>>]<
    NOT tmp >+<[[-]>-<]>[-<+>]<
    IF tmp [[-]
    go result <<
    INC result +
    DUP2 count <[->>+>+<<<]>>>[-<<<+>>>]<
    go tmp >
    ENDIF tmp ]
    go count <
    DEC count -
    go divisor <<<
    DEC divisor -
    ENDWHILE divisor ]
    // (divisor=0) dividend result=? count=?
    go count >>>
    sub from dividend [-<<->>]
    POP0 count <
    POP result [-]<
    DEC dividend -
    ADD [-<+>]<

    recht normal ist sowas wie den dividend so lange verdoppeln, bis er größer als der divisor ist. dann so lange halbieren, bis er weg ist und beim halbieren immer, wenn möglich, vom divisor abziehen. kostet O(log2(dividend)) subtraktionen, ist also schon relativ billig.

    0
  • V

    0
  • C

    Nun, ich möchte RSA (512-Bit) implementieren. Dafür habe ich mir eine Klasse (C++) geschrieben, die Zahlen unendlicher Größe verwalten kann.

    Bei Addition, Subtraktion und Multiplikation kann ich eine Zahl größer 64 bit aufspalten und mit dem Datentyp long rechnen. Bei Modulo und der darauf basierenden Division geht das nicht. Da muß ich den Zahlenstring mit einem Algorithmus bearbeiten, ... jedoch mit einem schnelleren, den ich jetzt verwende ...

    0
  • C

    Achja, an volkard vielen Dank, ist wirklich ein guter Gedanke! Wobei man den Algorithmus sogar noch schneller machen kann.

    1. Verdopple so lange den Divisor (dr) bis Dividend (dd) > dr und merke dir unverdoppelten Divisor (dr)
    2. wenn (dd - |dr|) > || (|drdr| - dd) gehe zu 2.a. andernfalls zu 2.b.
    wenn dr < dd breche ab (Ergebnis ist dr)

    2.a. Gehe zu 1. mit neuem Divisor |drdr| - dr

    2.b. Gehe zu 1. mit neuem Divisor dd - |dr|

    0
  • R

    Hallo ChrisPlusPlus

    Nun, ich möchte RSA (512-Bit) implementieren. Dafür habe ich mir eine Klasse (C++) geschrieben, die Zahlen unendlicher Größe verwalten kann.

    da haben wir uns doch die Arbeit doppelt gemacht. Ich hab mir eine Klasse "BigInt" geschrieben, bzw. ich bin noch dran. BigInt ist aber ein Fixpointformat mit x*32Bits Vorkommastellen und y*32Bits Nachkommastellen. Gestern habe ich SQRT() feriggestellt, wovor ich mich ein halbes Jahr gefürchtet habe und wobei mir dieses Forum die Initalialzündung gab. Momentan brauche ich MOD nicht, was sich aber ändern kann.

    Wäre es eine paraktikable Idee unseren Code zusammenzuschmeißen?

    Was ist RSA ?

    mfG
    rudiS

    0
  • C

    Was ist RSA ?

    http://de.wikipedia.org/wiki/RSA-Kryptosystem
    http://www.regenechsen.de/krypto/rsa.php

    Caipi

    0
  • C

    Hallo RudiS!

    Wäre mal neugierig auf Deine Implementierung! Jedoch, ich habe keinerlei Komprimierung innerhalb meiner Klassenverwaltungsklasse verwendet, möglicherweise ein fahrlässiger Mangel! Ich lasse beide Richtungen, links und rechts des Kommas offen und versuche diese Offenheit durch schnelle Algorithmen auszugleichen.

    Jedoch gibt es auch für die Quadratwurzel einen schönen Algorithmus, den ich Dir gerne näher bringen kann.

    Wenn Du willst kannst Du mir mal Deinen Code zusenden, ich werde Dir auch gerne meinen zukommen lassen.

    0
  • ?

    Hallo!

    Ich versuche etwas ähnliches. Ich will einen BCH Code (http://en.wikipedia.org/wiki/BCH_code) mit einer Länge von bis zu 4096bit verwirklichen.

    Dabei stosse ich auf die Aufgabe eine ca. 4000bit Zahl mit einer ca. 109bit lange Zahl Modulo zu rechnen (also eh sehr ähnlich zu CRC -> Siehe http://de.wikipedia.org/wiki/Zyklische_Redundanzprüfung
    Also sind die Zahlen auch leider keine bestimmten Potenz von einer kleinen Zahl.

    Diese lange Bitfolgen halt ich einfach mit einem Array von der entsprechenden Länge im Speicher:

    unsigned short infwort[xx];
unsigned short generator[x];

    Nun sollte ich eben den Rest rausbekommen - also:

    infowort % generator = Rest

    GMP hab ich mir schon angeschaut - aber um das zu verwenden müste ich, glaub ich mal, alles komplett umschreiben.

    Hat wer eine Idee wie ich langen Bitfolgen am erfolgreichsten und schnell Modulo rechne? Solange ich mich unter 64 bit bewegen würde, wäre die Aufgabe ja eh ziemlich einfach, aber da ja beide Zahlen darüber sind, seh ich mich gerade nicht aus.
    Versuche es jetzt schon länger und komm überhaupt nicht weiter....

    mfg
    erich

    0
  • P

    ah, jetzt ging kam endlich das Registrierungsmail.... 😉

    0
Anmelden zum Antworten