BigInteger problems

Question

Hello i am working on an algorithm for gcd and inverse modulo operations.

i have to use the BigInteger class but i have a few problems on this.

So could you help me please?

The problem is that by java programm doesnt want to overwrite the old BigInteger input with a new one.

    import java.math.BigInteger;
    public class Gcd
 { 
public static void gcd(BigInteger a, BigInteger b){
    BigInteger  modulo =  b;
    BigInteger  wert = a;
    BigInteger  zwischenwert1 =  BigInteger.valueOf(1);
    BigInteger  zwischenwert2 = BigInteger.valueOf(0);

    BigInteger  zwischenwert3 = BigInteger.valueOf(0);
    BigInteger  zwischenwert4 = BigInteger.valueOf(1);
    BigInteger negativ = BigInteger.valueOf(-1);
    BigInteger  q;
    do{
        q = modulo.divide(wert);

        wert = modulo.subtract(wert.multiply(q));           
        zwischenwert3 = zwischenwert1.subtract(zwischenwert3.multiply(q));
        zwischenwert4 = zwischenwert2.subtract(zwischenwert4.multiply(q));

        modulo = negativ.multiply((wert.subtract(modulo)).divide(q));
        zwischenwert1 = negativ.multiply((zwischenwert3.subtract(zwischenwert1)).divide(q));
        zwischenwert2 = negativ.multiply((zwischenwert4.subtract(zwischenwert2)).divide(q));         

    }while((modulo.signum()>1)&&(wert.signum()>1));
      System.out.println("gcd("+a+","+b+") = "+zwischenwert3+" * "+b+ " + "+ zwischenwert4+" * "+ a+" = "+((BigInteger.valueOf(b).multiply(zwischenwert3)).add((BigInteger.valueOf(a).multiply(zwischenwert4)))));
    if (((BigInteger.valueOf(b).multiply(zwischenwert3)).add((BigInteger.valueOf(a).multiply(zwischenwert4)))).signum()==1)
        System.out.println("Inverse "+a+" mod "+b+" is"+zwischenwert4);
    else
        System.out.println("no Inverse!");

}}

oh i am so sorry you are right it shoud be a and in the next lin b but this did not solve my problem of chainging the value of a BigInteger — user3233804, Jan 24 '14 at 23:03

score 5 · Answer 1 · answered Jan 24 '14 at 23:07

5

You don't have to write your own gcd method, as it is available in the BigInteger class.

a.gcd(b)

answered Jan 24 '14 at 23:07

Marcin Krupa

497
2
6

1

`modInverse` as well. – Niklas B. Jan 25 '14 at 04:10
[Yes he does](https://stackoverflow.com/questions/21343936/biginteger-problems#comment32179910_21344050), because it's probably an exercise from school. – phant0m Jan 25 '14 at 13:24

Giovanni Botta · Answer 2 · 2014-01-24T23:12:35.127

3

In java, all objects are passed by copy of reference, meaning if you pass a to your function and then change the value assigned to reference a, the original value will be unchanged, because you don't actually have access to the original reference, but a copy of it. You need to actually return a reference to the new object to let it escape the function.

For example:

public BigInteger mod(BigInteger a, BigInteger b){
  // .... create new value x
  return x;
}

By the way, as per the Wikipedia page, you can pretty much apply the following:

function gcd(a, b)
  while b ≠ 0
     t := b
     b := a mod b
     a := t
  return a

edited Jan 24 '14 at 23:12

answered Jan 24 '14 at 22:59

Giovanni Botta

9,626
5
51
94

Thanks for the fast answer ! but how can i do this ? Sorry i am new in the Java world – user3233804 Jan 24 '14 at 23:02
BTW you know that the `BigInteger` class has a method to compute the gcd? – Giovanni Botta Jan 24 '14 at 23:07
So every time i am calculating something like wert = modulo.subtract(wert.multiply(q)); i have to write return wert; ? – user3233804 Jan 24 '14 at 23:07
1

http://www.javaworld.com/article/2077424/learn-java/does-java-pass-by-reference-or-pass-by-value.html – MariuszS Jan 24 '14 at 23:08
Only when you're ready to exit the function. The return statement causes the program to exit the current function. – Giovanni Botta Jan 24 '14 at 23:09
jeah i know that it has this method but i have to write my own one – user3233804 Jan 24 '14 at 23:09
hmmm... the problem is the funktion doesnt go more than one time trough the do funktion – user3233804 Jan 24 '14 at 23:10
Figured. Read about the control flow in java. You have to start thinking more in a functional way than a procedural way (which "changing a reference" belongs to). – Giovanni Botta Jan 24 '14 at 23:10
hmmm ok thank you i will try it again and read something about it :) – user3233804 Jan 24 '14 at 23:17

BigInteger problems

2 Answers2