Letzten beiden Ziffern eines BigIntegers bestimmen?

[Wastl]

Hallo,

hab hier eine BigInteger Zahl. Wie bestimme ich möglichst effizient die letzten beiden Ziffern dieser Zahl?
Im Moment mache ich das noch so:

BigInteger r = new BigInteger("123433523423445812323473248762384");
String suffix = r.toString();
int lc1 = Integer.parseInt(suffix.substring(suffix.length()-2, suffix.length()-1));
int lc2 = Integer.parseInt(suffix.substring(suffix.length()-1, suffix.length()));

Diese Methode ist aber sehr ineffizient, leider.

 

[Wildcard]

chartAt sollte schonmal besser funktionieren

 

[Tellerrand]

public BigInteger mod(BigInteger m)
Liefert den Divisionsrest von diesem Objekt mit dem Divisor m in einem neuen BigInteger-Objekt zurück.
Exception: ArithmeticException
* Falls m kleiner gleich null ist.


Teile durch 100 und nehme den Rest.
Fraglich ist aber ob Modulo schneller ist :/

 

[Wildcard]

Fraglich ist aber ob Modulo schneller ist :/

Müsste man wohl ausprobieren....

 

[Wastl]

hm die Methode mit Modulo ist gut, funktioniert aber leider nicht wenn die Zahl z.B. so aussieht:
wenn beispielsweise r = 483485307

String suffix = r.mod(new BigInteger("100")).toString();
int lc1 = Integer.parseInt(suffix.substring(suffix.length()-2, suffix.length()-1));
int lc2 = Integer.parseInt(suffix.substring(suffix.length()-1, suffix.length()));[code]
denn dann ist suffix = 7 und dann gibts eine String index out of range exception

 

[Der Müde Joe]

if (suffux.lenght() == 1){
suffux = "0" + suffix;
}

e voilà
(gibt bessere (dynamische) lösungen ;-)

 

[Tellerrand]

hm die Methode mit Modulo ist gut, funktioniert aber leider nicht wenn die Zahl z.B. so aussieht:
wenn beispielsweise r = 483485307

String suffix = r.mod(new BigInteger("100")).toString();
int lc1 = Integer.parseInt(suffix.substring(suffix.length()-2, suffix.length()-1));
int lc2 = Integer.parseInt(suffix.substring(suffix.length()-1, suffix.length()));[code]
denn dann ist suffix = 7 und dann gibts eine String index out of range exception

Also wenn dann bitte:
int b = x.mod(new BigInteger("10")).intValue();
int a = x.mod(new BigInteger("100")).substract(b).divide(new BigInteger("10")).intValue();
oder so ähnlich kann es grad nicht testen.

Und ja, gibt bestimmt bessere Lösungen

 

[Wastl]

aja, so gehts.
allerdings ist die von mir oben gepostete methode immer noch schneller als der weg über modulo :-/

 

[Wildcard]

charAt versucht? Sollte zumindest schneller als die substring Variante sein, da du nur einen String aufbauen musst.

 

[Tellerrand]

Dann aml sowas in der Art
int b = x.mod(new BigInteger("10")).intValue();
int a = ((x.mod(new BigInteger("100")).intValue()) -b )/10;
da spart man sich ein wenig Zeugs.
Oder liegt es an der Modulo Operation an sich?

 

[Lim_Dul]

Wenn nur 1x module 100 und dann Auswerten, die modulo Operation dürfte teuer sein:

int a = (x.mod(new BigInteger("100")).intValue();
int letzteStelle = a % 10;
int vorletzteStelle = a/10;

(In Strings bitte selber umwandeln )

 

[Tellerrand]

Das kommt davon wenn man nicht nachdenkt bevor man schreibt :autsch:

Wobei ich glaube das Modulo je nach Implementierung von BigInteger recht schnell ist sein kann.
Aber ich weiß ja nciht was die da so mit getrieben haben

 

[Marco13]

Ach ja, ich immer mit meinen ausführlichen Antworten und Tests

Aber vielleicht interessiert's ja noch jemanden...

import java.math.*;


class BigIntegerTest
{

    static long runs = 1;
    public static void main(String args[])
    {
        BigInteger r = new BigInteger("123433523423445812323473248762384");
        for (runs = 1000; runs <= 1000000; runs*=10)
        {
            testA(r);
            testB(r);
            testC(r);
        }
    }


    private static void testA(BigInteger r)
    {
        long startTime = System.nanoTime();
        long result = 0;

        for (int i=0; i<runs; i++)
        {
            String suffix = r.toString();
            int lc1 = Integer.parseInt(suffix.substring(suffix.length()-2, suffix.length()-1));
            int lc2 = Integer.parseInt(suffix.substring(suffix.length()-1, suffix.length()));
            //System.out.println("A "+lc1+" "+lc2);
            result += lc1+lc2;
        }

        long estimatedTime = System.nanoTime() - startTime;
        System.out.println("A "+result+ " time "+(float)estimatedTime/1000000+" ms");
    }


    private static void testB(BigInteger x)
    {
        long startTime = System.nanoTime();
        long result = 0;

        for (int i=0; i<runs; i++)
        {
            int b = x.mod(new BigInteger("10")).intValue();
            int a = x.mod(new BigInteger("100")).subtract(new BigInteger(""+b)).divide(new BigInteger("10")).intValue();
            result += a+b;
            //System.out.println("B "+a+" "+b);
        }

        long estimatedTime = System.nanoTime() - startTime;
        System.out.println("B "+result+ " time "+(float)estimatedTime/1000000+" ms");
    }

    private static final BigInteger b100 = new BigInteger("100");

    private static void testC(BigInteger x)
    {
        long startTime = System.nanoTime();
        long result = 0;

        for (int i=0; i<runs; i++)
        {
            int y = (int)x.mod(b100).longValue();
            int a = y / 10;
            int b = y % 10;
            //System.out.println("C "+a+" "+b);
            result += a+b;
        }

        long estimatedTime = System.nanoTime() - startTime;
        System.out.println("C "+result+ " time "+(float)estimatedTime/1000000+" ms");
    }


}

 

[Wastl]

int a = (r.mod(new BigInteger("100")).intValue());
int lc1 = a%10;
int lc2 = a/10;

das ist leider auch langsamer als meine methode im ersten posting.

und charAt funktioniert irgendwie nicht:

String suffix = r.toString();
int lc1 = suffix.charAt(suffix.length()-2);
int lc2 = suffix.charAt(suffix.length()-1);

 

[Wastl]

Wow!
Marco13's C Methode ist mit Abstand am schnellsten! Danke!

 

[Wildcard]

@Marco13
Mehrere Tests in einem Durchlauf sind unzulässig da der Hotspot-Compiler deine Ergebnisse verfälscht :wink:

 

[Marco13]

Man weiß ja nicht, WO und WIE (in der "echten" Anwendung) diese Methode aufgerufen wird - die Alternative wäre, EINEN aufruf der Methode zu messen, und ob das so viel genauer wäre.... ? :wink:

 

[Lim_Dul]

Man weiß ja nicht, WO und WIE (in der "echten" Anwendung) diese Methode aufgerufen wird - die Alternative wäre, EINEN aufruf der Methode zu messen, und ob das so viel genauer wäre.... ? :wink:

Du müsstest testA, testB, testC getrennt aufrufen.

 

[Marco13]

Jedem, der das Programm laufen läßt, steht es frei, jeweils ZWEI der drei Zeilen testA/testB/testC auszukommentieren, und die Tests getrennt zu machen :wink: Allerdings sind die Unterschiede aufgrund des Programmablaufes (größer werdende Testfälle, viele Durchläufe) ziemlich schnell vernachlässigbar gering:

A 12000 time 59.076794 ms
B 12000 time 23.715015 ms
C 12000 time 1.223878 ms
A 120000 time 33.12588 ms
B 120000 time 35.016804 ms
C 120000 time 9.428851 ms
A 1200000 time 264.51123 ms
B 1200000 time 255.88014 ms
C 1200000 time 66.320564 ms
A 12000000 time 2444.4995 ms
B 12000000 time 2382.9854 ms
C 12000000 time 584.097 ms


A 12000 time 32.478184 ms
A 120000 time 37.2518 ms
A 1200000 time 272.8278 ms
A 12000000 time 2489.099 ms

B 12000 time 36.837086 ms
B 120000 time 40.783295 ms
B 1200000 time 269.23645 ms
B 12000000 time 2383.6587 ms

C 12000 time 8.278429 ms
C 120000 time 15.750715 ms
C 1200000 time 70.19173 ms
C 12000000 time 598.4957 ms

 

[Tellerrand]

Bei dem Test stellt sich doch erstmal die Frage was der JIT Compiler macht.

Kenn mich zwar mit den Optimierungsmethoden des JIT C nicht aus, aber da ist doch so einiges nicht sicher.

Wenn ich mir sowas anschaue stellen sich mir jedenfalls einige Fragen
C 12000 time 8.278429 ms
C 120000 time 15.750715 ms
C 1200000 time 70.19173 ms
C 12000000 time 598.4957 ms

 

[Marco13]

Naja - bei den ersten beiden schlägt auch noch die Ungenauigkeit des Timers zu - auch wenn es "nanoTime" heißt, kann er schon mal 10 oder 20 ms falsch liegen (darum auch Tests mit VIELEN Durchläufen). Zumindest zwischen den letzten beiden ist der Faktor "ungefähr" 10, was man ja erwarten würde...
EDIT: Geschrieben hatte ich das auf einem Rechner, der ca. 3 mal so langsam war, wie der, wo ich jetzt die neuen Testläufe gemacht habe, d.h. da fielen auch beim 2. Durchlauf diese Ungenauigkeiten noch nicht sooo ins Gewicht (und NOCH ein 10x so langer Durchlauf wäre mir auf dem anderen Rechner zu langweilig geworden :wink: )