?
Solved

Problem applying modulus(%) to a BigInteger

Posted on 2005-03-29
43
Medium Priority
?
419 Views
Last Modified: 2010-04-16
Hi All,

Can anyone help me with a work around?



double y1 = (Math.pow(x1, x2)) % x3;

where x1, x2 are integers and x3 is a BigInteger


Thanxs
Garion
0
Comment
Question by:yongeng
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 16
  • 13
  • 6
  • +3
43 Comments
 
LVL 86

Expert Comment

by:CEHJ
ID: 13651631
Try

% x3.doubleValue();
0
 
LVL 6

Expert Comment

by:mightyone
ID: 13651681
double y1 = (Math.pow(x1, x2)) % (double)x3;

or

double y1 =(double)(((BigInteger) (Math.pow(x1, x2))) % x3);



0
 
LVL 37

Expert Comment

by:zzynx
ID: 13652163
mightyone,
that results twice in
  inconvertible types

You can't cast a double to a BigInteger and vice versa
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 15

Expert Comment

by:aozarov
ID: 13655681
double y1 = (Math.pow(x1, x2)) % x3;

where x1, x2 are integers and x3 is a BigInteger

double y1 = Math.pow(x1, x2) % x3.longValue();
// or x3.intValue(); if you know the number can be stored in an int.
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 13659024
You will have to make the assumption that the BigInteger value holds something which is not greater than the range of long and optimistically use longValue (). Though I don't think that this would help in your case (if it was a value within the range of long that you wanted to store, why would you use a BigInteger in the first place?).

By the way, you might be better of converting the result of Math.pow () into a BigInteger and using the remainder () method provided by the BigInteger class.
0
 
LVL 30

Assisted Solution

by:Mayank S
Mayank S earned 400 total points
ID: 13659036
BigInteger bigInt = new BigInteger ( Long.toString ( Math.pow ( x1, x2 ) ) ) ;
BigInteger remainder = bigInt.remainder ( x3 ) ;
int r = remainder.intValue () ; // or long r = remainder.longValue () ;
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659047
I assumed that x3 BigInteger was given to him (argument or someting like that).
If x3 may hold values bigger then long (which actually I doubt that is the case for a module value) then Yes you can take
the approach of using only BigInteger calculation.
somethig like that:
BigInteger result = new BigInteger(x1).modPow(new BigInteger(x2). x3);
you can always call result.longValue() or result.intValue()
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659080
mayankeagle, I think remainder works differently then mod when it comes to negative values.
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 13659092
>> I think remainder works differently then mod when it comes to negative values.

Does it? Not sure as I never tried it. But anyway, why should it? Anyway, I hope that is not the case here :)

>> If x3 may hold values bigger then long (which actually I doubt that is the case for a module value)

In that case, why to make a BigInteger after all :) just store it as a 'long'. yongeng, what is the case?
0
 

Author Comment

by:yongeng
ID: 13659112
>> In that case, why to make a BigInteger after all :) just store it as a 'long'. yongeng, what is the case?

Hi mayankeagle,

would there a difference stroing my integer as long?

the value input would be a very large value.....

how do I declare it as a long interger?

Thanxs
Garion
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659126
Yes, there is difference:
From java sources:
reminder -> divide(this, val, null, rem, TRUNCATE);
mod -> divide(this, m, null, rem, FLOOR);

and the rounding logic:
switch (rounding_mode)
703     {
704     case TRUNCATE:
705       break;
706     case CEILING:
707     case FLOOR:
708       if (qNegative == (rounding_mode == FLOOR))
709         add_one = true;
710       break;
711     case ROUND:
712       add_one = r > ((y - (q & 1)) >> 1);
713       break;
714     }

Also, because such operation of pow and mod is so common (RSA,...) they have one method for it as I meantioned "modPow"
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659134
I think you should go all the way with BigInteger so you will not have any "trancation" problems.
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 13659148
>> would there a difference stroing my integer as long?

Why are you using a BigInteger in the first place? Perhaps because the values are very large?

>> how do I declare it as a long interger?

long x3 ; // just like any other variable-declaration - but do that only if you know that the value will fit in it

>> the value input would be a very large value

If it is bigger than a 'long', then you should use BigInteger the way you are using. And if it will always be a positive value, then you could use the remainder () method as I had shown.
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659165
mayankeagle, man you are living on the edge ;-)
Good night.
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659173
I was talking about the reminder thing (if you didn't get my joke) no offend :-)
0
 

Author Comment

by:yongeng
ID: 13659248
>>BigInteger bigInt = new BigInteger ( Long.toString ( Math.pow ( x1, x2 ) ) ) ;
>>BigInteger remainder = bigInt.remainder ( x3 ) ;
>>int r = remainder.intValue () ; // or long r = remainder.longValue () ;

Hi mayankeagle,

Can you explain this? I dun realli understand how it works.....

When I run it, i got an error for line 1.... saying "cannot resolve symbol
symbol  : method toString (double)"
0
 

Author Comment

by:yongeng
ID: 13659274
>>BigInteger result = new BigInteger(x1).modPow(new BigInteger(x2). x3);

When I tried this, it compiles with the same error.....
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 13659285
Try: BigInteger bigInt = new BigInteger ( Double.toString ( Math.pow ( x1, x2 ) ) ) ;
0
 

Author Comment

by:yongeng
ID: 13659303
>> Try: BigInteger bigInt = new BigInteger ( Double.toString ( Math.pow ( x1, x2 ) ) ) ;


thanxs....

it compiles with no errors now, but when i run it with the test values, it terminates with an error.....
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 13659325
What is the error that it gives? Please post your updated code.
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659341
Right, sorry BigInteger doesn't accept integer in the constuctor (but does accept string).
See that:
import java.math.*;

public class Tmp
{
public static void main(String st[]) throws Exception
{
int x1 = 12;
int x2 = 2;
BigInteger x3 = new BigInteger("5");
BigInteger result = new BigInteger(String.valueOf(x1)).modPow(new BigInteger(String.valueOf(x2)), x3);
System.out.println(result);
}
}

output:
knoppix@ttyp1[knoppix]$ javac Tmp.java
knoppix@ttyp1[knoppix]$ java Tmp
4
0
 

Author Comment

by:yongeng
ID: 13659349
Hi mayankeagle,

The error is "Exception in thread "main" java.lang.NumberFormat Exception: For inout string: "Infinity" ........"

my updated code is:
BigInteger bigInt = new BigInteger ( Double.toString ( Math.pow ( x1, x2 ) ) ) ;
BigInteger remainder = bigInt.remainder ( x3 ) ;
int r = remainder.intValue () ; // or long r = remainder.longValue () ;


thanxs
0
 

Author Comment

by:yongeng
ID: 13659372
Hi aozarov,

I tried to change the codes to yours but after running with the test values, the result is always 0....
0
 

Author Comment

by:yongeng
ID: 13659423
>> I tried to change the codes to yours but after running with the test values, the result is always 0....

sorrie aozarov, i mixed up the values.... it working now :)
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659439
:-)
0
 

Author Comment

by:yongeng
ID: 13659457
hi aozorov,

can you roughly explain how it the statement works?

espacially the modPow....
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659487
x.modPow(y,z) is doing exactly: (x ^ y) % z
or in words: (x power y) mod z.
It is added to the JDK because it is a common thing to do in cryptography.
If you look at BigInteger API you see many other related methods (like isPrime ....)
0
 

Author Comment

by:yongeng
ID: 13659523
thanxs aozarov..... you have been a great help :)


would like to consult you on one last question on this topic.....

I tried to modify your statement to calculate   ((x ^ y)*a) % z
 but I was prompted with the error that "operator * cannot be applied to bigInteger".... is there a work around?
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659556
Yes. Use BigIntger       multiply(BigInteger val)  function.

chage:
BigInteger result = new BigInteger(String.valueOf(x1)).modPow(new BigInteger(String.valueOf(x2)), x3);

to (assuming a is also integer):

BigInteger result = new BigIntger(String.valueOf(x1)).pow(new BigInteger(String.valueOf(x2))).multiply(new BigIntger(String.valueOf(a))).mod(x3);

This time I didn't use modPow directly but rather first pow then mod because you want to mod ((x ^ y) * a), right?
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659580
Small correction:
the line should be:
new BigInteger(String.valueOf(x1)).pow(x2).multiply(new BigInteger(String.valueOf(a))).mod(x3);

I had 2 spelling mistakes Intger -> Integer.
and also pow seems to accept integer and not BigInteger.
0
 
LVL 15

Accepted Solution

by:
aozarov earned 1200 total points
ID: 13659586
import java.math.*;

public class Tmp
{
public static void main(String st[]) throws Exception
{
int x1 = 12;
int x2 = 2;
BigInteger x3 = new BigInteger("5");
BigInteger result = new BigInteger(String.valueOf(x1)).modPow(new BigInteger(String.valueOf(x2)), x3);
System.out.println(result);
int a = 2;
result = new BigInteger(String.valueOf(x1)).pow(x2).multiply(new BigInteger(String.valueOf(a))).mod(x3);
System.out.println(result);
}
}

knoppix@ttyp1[knoppix]$ javac Tmp.java
knoppix@ttyp1[knoppix]$ java Tmp
4
3

0
 

Author Comment

by:yongeng
ID: 13659590
it compiles with an error "pow(int) in java.math.BigInteger cannot be applied to (java.math.BigInteger)"
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659600
And another thing:

if you have integer you don't have to do: new BigInteger(String.valueOf(x1)) to convert it into BigInteger
you can just do: BigInteger.valueOf(x1);

So, basically the following line is equal (but shorter) to what we did before

result = BigInteger.valueOf(x1).pow(x2).multiply(BigInteger.valueOf(a)).mod(x3);
0
 

Author Comment

by:yongeng
ID: 13659622
hi aozarov,

a is also a big integer.....

i tried to change it to
BigInteger result3 = new BigInteger(String.valueOf(x1)).pow(x2).multiply(new BigInteger(String.valueOf(a))).mod(x3);

but its still giving the same error....
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13659673
Oh, if a is big integer then you need to do:
BigInteger result3 = new BigInteger(String.valueOf(x1)).pow(x2).multiply(a).mod(x3);

or just
BigInteger result3 = BigInteger.valueOf(x1).pow(x2).multiply(a).mod(x3);
0
 
LVL 37

Assisted Solution

by:zzynx
zzynx earned 400 total points
ID: 13659934
>> it compiles with an error "pow(int) in java.math.BigInteger cannot be applied to (java.math.BigInteger)"

You can convert this BigInteger to an int via intValue()

so change
   pow(x2)
into
   pow(x2.intValue())
0
 

Author Comment

by:yongeng
ID: 13660029
sorry aozarov, but its still giving the same error......

BigInteger result3 = new BigInteger(String.valueOf(x1)).pow(x2).multiply(a).mod(x3);

all the variables: x1, x2, x3 and a are supppose to be BigInteger.....
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13660080
As I said:

change
   pow(x2)
into
   pow(x2.intValue())
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13660084
pow() doesn't take a BigInteger as parameter but an int
0
 

Author Comment

by:yongeng
ID: 13660130
thanxs zzynx.... its working now....

sorrie i din read carefully......
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13660152
>> thanxs zzynx.... its working now....
Good

>> sorrie i din read carefully......
I happens to all of us ;°)
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13660212
Thanks
0
 
LVL 15

Expert Comment

by:aozarov
ID: 13662095
I am happy to hear that it worked for you (thanks zzynx).
BTW, was not x2 originally integer?
>>  where x1, x2 are integers and x3 is a BigInteger
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…
Suggested Courses
Course of the Month7 days, 23 hours left to enroll

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question