Optimierung von Potenzen und Modulo !!

HI all,

ICh stelle diese Frage lieber im Mathe-Forum, evt. stoß ich hier eher auf Hilfe !

ich hab hier ein ziemliches Problem. Ich muss ein Algorithmus finden der sehr schnell und effektiv ist für die Modulo bzw. Potenz funktion.

Die 0815 Methoden brauchen mir zu lange !!

Erstmal:
Ich potenziere IMMER nur zur Basis 2 !!
=>2^5, oder 2^0 ..usw

Ich habe eine Schleife die in etwa so aussieht:
------

for( runde=0; runde < 11; runde++ )
{
    for( member=0; member < 1024; member ++ )
    {
        __CODE__
    }
}

Im __CODE__ führe ich dann mehere Potenz bzw. Modulo operationen durch.

..

if( $iMember >= (int)(pow( 2, $i )-1) )
..

if( $numItems % pow( 2, $i+1) == 0 )
...

if( $counter < (pow( 2, $i+1 )+1) )

Ist euch euch guter Algorihmus bekannt der evt. mir da weiterhelfen könnte ?

Ciao

Michael E.

Beim Potenzieren zur Basis 2 kannst du einfach Bitverschiebung machen.

Irgendwie bin ich darauf nicht gekommen : THX !!

So nun das Modulo...

Eine Modulo operation wird immer mit einer 2er potenz ausgeführt..d.h.

if( (X % zweier_potenz) == 0 )

wobei X eine beliebige zahl ist...

Ciao

Hi,

ich sehe gerade, dass die Modulo operation nicht die Zeit in anspruch nimmt, sondern die Übergabe von einem true/false an ein array !!

estmal danke, an alle die sich damit beschäftigt haben !!

Dommel

auch wenn du es jetzt nicht mehr brauchst...

müsste man beim modulo mit 2^n nicht einfach die n hinteren stellen überprüfen??
Allerdings wüsste ich nicht, wie man da rankommt...

henselstep

x n-mal nach recht shiften, n-mal nach links shiften, und von x abziehen

Kann man nicht mit bitweisem UND was machen??
Also eine Bitmaske mit n Einsen am Ende(wenns nur Zweierpotenzen sind),
und dann
Modulo = Zahl && Bitmaske;

Obwohl das Erstellen der Bitmaske wahrscheinlich lange dauert.

int Bitmaske = 2^n-1;
int modulo = Zahl && Bitmaske;

Ich weiß nicht, ob da nicht die "08/15"-Methoden wirklich schneller sind.

Jester

japp, das geht auch.

2^n kriegt man bequem per 1<<n.
Nur für die UND-Verknüpfung solltest Du lieber & statt && verwenden, da das sonst nicht bitweise passiert.