Results 1 to 20 of 20
  1. #1
    sgtlaugh is offline Member
    Join Date
    Dec 2011
    Posts
    12
    Rep Power
    0

    Default Get first 40 digits of a BigInteger

    Hi, I need to write a program for which I need to get the first 40 digits of many BigInteger numbers, say about 100000 So, I can generate all these numbers in less than 2 seconds, but how do I get
    the first 40 digits of all the numbers? I tried using toString(), it works but it is very very slow. I need something faster please help!

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,572
    Rep Power
    25

    Default Re: Get first 40 digits of a BigInteger

    Which are the first 40? From the left or from the right end of the number?
    Can you post a SSCCE that compiles and demonstrates your problem?

  3. #3
    sgtlaugh is offline Member
    Join Date
    Dec 2011
    Posts
    12
    Rep Power
    0

    Default Re: Get first 40 digits of a BigInteger

    The first 40 digits. Actually I need to get the first 40 digits of the first 100000 Fibonacci numbers. Sorry, but how to write a
    SSCCE? I am actually new here, sorry for my lack of knowledge :(

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,572
    Rep Power
    25

    Default Re: Get first 40 digits of a BigInteger

    Google gives this: Short, Self Contained, Correct Example

    To work on the problem we need code.

    How many Fibonacci numbers do you need before you get one that has 40 digits?

  5. #5
    sgtlaugh is offline Member
    Join Date
    Dec 2011
    Posts
    12
    Rep Power
    0

    Default Re: Get first 40 digits of a BigInteger

    Java Code:
    import java.io.*;
    import java.util.*;
    import java.math.BigInteger;
    
    public class Main {
    	public static void main(String[] args){
    		BigInteger temp = BigInteger.valueOf(1);
    		BigInteger temp2 = BigInteger.valueOf(2);
    		BigInteger []ar;
    		ar = new BigInteger[100010];
    		ar[0] = temp;
    		ar[1] = temp2;
    
    		for (int i = 2; i <= 100005; i++){
    			BigInteger res = temp.add(temp2);
    			BigInteger temp3 = temp2;
    			temp2 = res;
    			temp = temp3;
    			String str = res.toString(); // This is the line which slows done the whole code in my opinion.
    		}
    	}
    }
    Here's a part of my code, any help would be appreciated. Thanks a lot :)
    Last edited by Norm; 12-13-2011 at 09:22 PM. Reason: added code tags

  6. #6
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,572
    Rep Power
    25

    Default Re: Get first 40 digits of a BigInteger

    What is the purpose of creating the String: str if you never use it?

    If you remove the last statement in the loop, it will run faster.

  7. #7
    sgtlaugh is offline Member
    Join Date
    Dec 2011
    Posts
    12
    Rep Power
    0

    Default Re: Get first 40 digits of a BigInteger

    My plan was to get the first 40 digits of the numbers using str.substring(0, 40); But just the conversion to a string takes a whole lot of time so I omitted the latter part. How can I achieve this more efficiently?

  8. #8
    2by4 is offline Banned
    Join Date
    Dec 2011
    Posts
    143
    Rep Power
    0

    Default Re: Get first 40 digits of a BigInteger

    Why have you got a huge array with only two values populated?

  9. #9
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,572
    Rep Power
    25

    Default Re: Get first 40 digits of a BigInteger

    You need to post the code you are having the problem with.

    The code you posted does not use the String str so it makes no sense to have it in the code.

  10. #10
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,572
    Rep Power
    25

    Default Re: Get first 40 digits of a BigInteger

    The array isn't used in the loop either. It looks completely redundant.

  11. #11
    sgtlaugh is offline Member
    Join Date
    Dec 2011
    Posts
    12
    Rep Power
    0

    Default Re: Get first 40 digits of a BigInteger

    Ok here goes my whole code.

    Java Code:
    import java.io.*;
    import java.util.*;
    import java.math.BigInteger;
    
    
    public class Main {
    	public static void main(String[] args){
    		BigInteger temp = BigInteger.valueOf(1);
    		BigInteger temp2 = BigInteger.valueOf(2);
    		BigInteger []ar;
    		ar = new BigInteger[100010];
    		ar[0] = temp;
    		ar[1] = temp2;
    
    
    		for (int i = 2; i <= 100005; i++){
    			BigInteger res = temp.add(temp2);
    			BigInteger temp3 = temp2;
    			temp2 = res;
    			temp = temp3;
    			String str = res.toString(); // This is the line which slows done the whole code in my opinion.
    			int len = str.length();
    			int flag;
    			if (len < 40) flag = len;
    			else flag = 40;
    			String substring = str.substring(0, flag);
    			BigInteger ans = new BigInteger(substring);
    			ar[i] = ans;
    			//System.out.println(ans);
    		}
    	}
    }
    Last edited by sgtlaugh; 12-13-2011 at 09:36 PM. Reason: Forgot code tag

  12. #12
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,572
    Rep Power
    25

    Default Re: Get first 40 digits of a BigInteger

    Can you detect if the value of a BigInteger has > 40 decimal digits and use division to remove the low order digits you don't want.

  13. #13
    sgtlaugh is offline Member
    Join Date
    Dec 2011
    Posts
    12
    Rep Power
    0

    Default Re: Get first 40 digits of a BigInteger

    Yes I tried division, it is slow like toString() because I have to perform it about 100,000 times

  14. #14
    sgtlaugh is offline Member
    Join Date
    Dec 2011
    Posts
    12
    Rep Power
    0

    Default Re: Get first 40 digits of a BigInteger

    I also tried using BigInteger.shiftRight(int bits) to trim result, but I don't know how to achieve this. It would have been much faster but I don't know if it's possible

  15. #15
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,572
    Rep Power
    25

    Default Re: Get first 40 digits of a BigInteger

    You can't shift binary bits an even number of decimal digits.

  16. #16
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,572
    Rep Power
    25

    Default Re: Get first 40 digits of a BigInteger

    Can you post the code you used with the division?

  17. #17
    sgtlaugh is offline Member
    Join Date
    Dec 2011
    Posts
    12
    Rep Power
    0

    Default Re: Get first 40 digits of a BigInteger

    Okay but how to solve my problem now? Any suggestions?

  18. #18
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,572
    Rep Power
    25

    Default Re: Get first 40 digits of a BigInteger

    That's what I'm working on.

  19. #19
    sgtlaugh is offline Member
    Join Date
    Dec 2011
    Posts
    12
    Rep Power
    0

    Default Re: Get first 40 digits of a BigInteger

    Sorry, I closed the division program and later reopened it and modified it to create this string program. I can of course re-write it but I must go now. I'll check here later, please post a solution if you find any. Thanks a lot for your time and help, bye for now.

  20. #20
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,572
    Rep Power
    25

    Default Re: Get first 40 digits of a BigInteger

    I'll wait for your post of the division code

Similar Threads

  1. Replies: 19
    Last Post: 11-10-2011, 06:43 AM
  2. Replies: 3
    Last Post: 10-27-2011, 05:23 PM
  3. BigInteger
    By 7cardcha in forum New To Java
    Replies: 9
    Last Post: 10-25-2011, 06:06 AM
  4. Replies: 1
    Last Post: 01-19-2011, 09:23 PM
  5. BigInteger
    By windows.login in forum New To Java
    Replies: 8
    Last Post: 07-13-2010, 01:10 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •