GPU-Computing

Langzahlen-Arithmetik

 aufwärts

Typ BigInt: Darstellung als Array von int-Zahlen

Lange positive ganze Zahlen werden als Array p fester Länge von Zahlen vom Typ int dargestellt (in C vom Typ unsigned int), also von 32-Bit-Wörtern. Die Länge size dieses Arrays ist als Klassen­variable fest eingestellt (z.B. size = 8). Die tatsächliche Länge einer Zahl ohne führende 0-Wörter wird durch die Objekt­variable len angegeben. Für die Zahl 0 gilt len = 0. Mit der Methode normalize wird der Wert von len gesetzt.

Im Konstruktor wird zunächst nur das Array p angelegt und mit Nullen vorbesetzt. Der Wert von len kann erst bei tat­sächlicher Zuweisung eines Wertes gesetzt. werden. Ein weiterer Konstruktor dient als Copy-Konstruktor.

Mithilfe von Factory-Methoden createBigInt werden Zahlen vom Typ int, long oder BigInteger in den Typ BigInt umgewandelt.

public class BigInt implements Comparable
{
    public static int size=8;   // Länge des Arrays (fest)
    public int[] p;    // Array von 32-Bit-Zahlen
    public int len;    // tatsächliche Länge der Zahl ohne führende Nullen
                       // Darstellung der 0: len=0

    public static BigInt ONE = createBigInt(1);

    // Konstruktor
    public BigInt()
    {
        p=new int[size];
        len=0;
    }

    // Copy-Konstruktor
    public BigInt(BigInt b)
    {
        this();
        len=b.len;
        for (int i=0; i<len; i++)
            p[i]=b.p[i];
    }

    // Factory-Methoden

    // ... aus int
    public static BigInt createBigInt(int b)
    {
        BigInt cc=new BigInt();
        cc.p[0]=b;
        cc.normalize();
        return cc;
    }

    // ... aus long
    public static BigInt createBigInt(long b)
    {
        BigInt cc=new BigInt();
        cc.p[0]=(int)b;
        cc.p[1]=(int)(b>>>32);
        cc.normalize();
        return cc;
    }

    // ... aus BigInteger
    public static BigInt createBigInt(BigInteger b)
    {
        BigInt cc=new BigInt();
        cc.len=(b.bitLength()+31)/32;
        for (int i=0; i<cc.len; i++)
        {
            cc.p[i]=b.intValue();
            b=b.shiftRight(32);
        }
        return cc;
    }

    // ...

Arithmetik-Operationen

Die folgende Additions-Operation ist das Kernstück der Arithmetik-Operationen.

Bei der Addition entsteht ein Übertrag, wenn die beiden Summanden mit einer 1 beginnen oder wenn einer der beiden Summanden mit einer 1 beginnt, aber das Ergebnis mit einer 0 beginnt. Die ent­sprechende Wahrheits­tafel für den Übertrag carry bei den jeweils ersten Bits der Summanden a und b sowie des Ergebnisses c ist die folgende:

abccarry
0000
0010
0101
0110
1001
1010
1101
1111

Die logische Formel für carry lautet somit ab + ac + bc. Die ent­sprechenden Bit-Operationen werden auf die gesamten 32-Bit-Operanden a, b und c und damit insbesondere auf die jeweils ersten Bits angewendet. Das Ergebnisbit ist genau dann gleich 1, wenn die zugehörige 32-Bit-Zahl negativ ist. Dies führt zu der Anweisung carry=(a&b | a&~c | b&~c)<0;.

 

    // Arithmetik-Operationen

    // addiert bb um k Wörter nach links geschoben zu this
    // bei subtract=true wird subtrahiert
    public void addTo(BigInt bb, int k, boolean subtract)
    {
        int a, b, c;
        boolean carry=subtract;
        for (int i=k; i<bb.len+k; i++)
        {
            a=p[i];
            b=bb.p[i-k];
            b=subtract? ~b: b;    // Einer-Komplement bei Subtraktion
            c=a+b;
            if (carry) c+=1;
            carry=(a&b | a&~c | b&~c)<0;
            p[i]=c;
        }
        // Übertrag weiter fortpflanzen
        for (int i=bb.len+k; carry && i<bb.len+len; i++)
        {
            a=p[i];
            b=subtract? -1: 0;       // Einer-Komplement bei Subtraktion
            c=a+b+1;
            carry=(a&b | a&~c | b&~c)<0;
            p[i]=c;
        }
        normalize();
    }

    // addiert bb um k Wörter nach links geschoben zu this
    public void addTo(BigInt bb, int k)
    {
        addTo(bb, k, false);
    }

    // addiert b um k Wörter nach links geschoben zu this
    public void addTo(long b, int k)
    {
        addTo(BigInt.createBigInt(b), k);
    }

    // addiert bb zu this
    public void addTo(BigInt bb)
    {
        addTo(bb, 0);
    }

    // addiert zwei Zahlen
    public BigInt add(BigInt bb)
    {
        BigInt c=new BigInt(this); // Copy-Konstruktor
        c.addTo(bb);
        return c;
    }

    // subtrahiert zwei Zahlen
    public BigInt sub(BigInt bb)
    {
        BigInt c=new BigInt(this); // Copy-Konstruktor
        c.addTo(bb, 0, true);
        return c;
    }

    // multipliziert zwei Zahlen
    public BigInt mul(BigInt bb)
    {
        long c;
        BigInt cc=new BigInt();
        for (int i=0; i<len; i++)
            for (int j=0; j<bb.len; j++)
            {
                c=p[i] & 0xffffffffL;         // unsigned
                c=c*(bb.p[j] & 0xffffffffL);  // unsigned
                cc.addTo(c, i+j);
            }
        return cc;
    }

    // multipliziert mit einer int-Zahl
    public BigInt mul(int b)
    {
        return mul(BigInt.createBigInt(b));
    }

    // ...

Sonstige Operationen

 

   // schiebt eine BigInt-Zahl um k Wörter nach rechts
    public BigInt rightWordShift(int k)
    {
        BigInt cc=new BigInt();
        for (int i=0; i<len-k; i++)
            cc.p[i]=p[i+k];
        cc.normalize();
        return cc;
    }

    // schiebt eine BigInt-Zahl um k Wörter nach links
    public BigInt leftWordShift(int k)
    {
        BigInt cc=new BigInt();
        for (int i=k; i<len+k; i++)
            cc.p[i]=p[i-k];
        cc.normalize();
        return cc;
    }

    public BigInteger toBigInteger()
    {
        BigInteger s;
        BigInteger x=BigInteger.ZERO;
        for (int i=0; i<len; i++)
        {
            s=BigInteger.valueOf(p[i] & 0xffffffffL);   // unsigned
            s=s.shiftLeft(i*32);
            x=x.add(s);
        }
        return x;
    }

    @Override
    public String toString()
    {
        return toBigInteger().toString();
    }

    // liefert den Bitstring einer int-Zahl
    private String getBitString(int a)
    {
        String w=Integer.toBinaryString(a);
        w="00000000000000000000000000000000"+w;   // führende Nullen einfügen
        w=w.substring(w.length()-32);
        return w;
    }

    // liefert den Bitstring der BigInt-Zahl this
    public String getBitString()
    {
        String v="";
        for (int i=0; i<len; i++)
            v=getBitString(p[i])+" "+v;
        return v;
    }

    // liefert die Länge (in Wörtern) ohne führende 0-Wörter
    public int getLen()
    {
        for (int i=size-1; i>=0; i--)
            if (p[i]!=0)
                return i+1;
        return 0;
    }

    // entfernt führende 0-Wörter
    public void normalize()
    {
        len=getLen();
    }

    // prüft auf Gleichheit mit einer BigInteger-Zahl
    public boolean isEqualTo(BigInteger aa)
    {
        return this.toBigInteger().equals(aa);
    }

    @Override
    public int compareTo(Object b)
    {
        BigInt c=(BigInt)b;    // cast to BigInt
        int k0=getLen(), k1=c.getLen();
        if (k0>k1)
            return 1;
        if (k0<k1)
            return -1;
        for (int i=k0; i>=0; i--)
        {
            if (p[i]>c.p[i])
                return 1;
            if (p[i]<c.p[i])
                return -1;
        }
        return 0;
    }

    // ...

Test

 

    public static void main(String[] args)
    {
        BigInt x=new BigInt();
        BigInt y=new BigInt();
        BigInt t;
        x.p[0]=3;
        x.p[1]=900;
        x.p[2]=2340;
        x.p[3]=234500;
        x.normalize();
        System.out.println("x: " + x);

        y.p[0]=12345;
        y.p[1]=6780;
        y.p[2]=86780;
        y.p[3]=8766780;
        y.normalize();
        System.out.println("y: " + y);

        t=x.mul(y);
        System.out.println("BigInt:     " + t);

        BigInteger xx, yy, tt;
        xx=x.toBigInteger();
        yy=y.toBigInteger();
        tt=xx.multiply(yy);
        System.out.println("BigInteger: " + tt);

        assert t.isEqualTo(tt);
    }

}

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 31.08.2014   Updated: 07.06.2018
Valid HTML 4.01 Transitional