Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Seeking for better algo

  1. #1
    Member
    Join Date
    Oct 2013
    Location
    Manila, Philippines
    Posts
    285
    My Mood
    Amused
    Thanks
    6
    Thanked 64 Times in 61 Posts

    Default Seeking for better algo

    hi everyone

    i'm writing a program that generates 2 to the power of 7830457.
    well, i'm not sure if BigInteger class can support this,
    here is my code using BigInteger
    BigInteger base = new BigInteger("2"),
                    two = new BigInteger("2");
    int expo = 2;
    base = base.pow(7830457);
    System.out.println(base);
    but that code takes too much time to execute.

    here my code using simple mathematics algorithm.
            char[] digits = new char[2357207];
            digits[0] = '2';
            int carryOver = 0, i, num;
            for (int expo = 2; expo <= 100; expo++) {
                i = 0;
                while (digits[i] != 0 || carryOver != 0) {
                    num = digits[i] - 48;
                    if(num < 0) {
                        num = 0;
                    }
                    num *= 2;
                    num += carryOver;
                    carryOver = num / 10;
                    num = num % 10;
                    num += 48;
                    digits[i++] = (char) num;
                }
            }
            StringBuilder sb = new StringBuilder();
            i = 0;
            while(digits[i] != 0) {
                sb.append(Integer.toString(digits[i++] - 48));
            }
            sb.reverse();
            System.out.println(sb);

    i'm pretty much sure with my algorithm, because i've tested it with different exponents.
    but the problem is when the exponent is consist of 6 digits and above, it took too much time
    to execute. And according to the guidelines, all problem can be executed within a minute.

    I'm asking if there's a better algorithm that can do the same thing in less than a minute?
    just the IDEA please
    Thank you so much..

    Note: The goal of this exercise is not to get the exact value of 2 to the power
    of 7830457 but to get the last 10 digits of that value.


  2. #2
    Junior Member
    Join Date
    Dec 2013
    Posts
    2
    Thanks
    0
    Thanked 1 Time in 1 Post

    Default

    Kind of a math problem, more than a programming one. I'll do the math and let you figure out the programming part if you don't want spoilers.

    Think about it this way: If you're only trying to find the last ten digits, then mathematically any digits after the tenth will have no impact on the digits before them if you're only doubling. So don't worry about them.

    Start with 2, 4, 8, 16, and so on, then when your number gets above ten digits just subtract off 10000000000, then double what you have left. The remaining ten digit number will be equal to the last ten digits of your final number. Program-wise you should be able to do it in a minute, no sweat.

  3. The Following User Says Thank You to CampwideGames For This Useful Post:

    dicdic (December 3rd, 2013)

  4. #3
    Forum VIP
    Join Date
    Jun 2011
    Posts
    395
    My Mood
    Busy
    Thanks
    49
    Thanked 112 Times in 95 Posts
    Blog Entries
    5

    Default Re: Seeking for better algo

    I was about to suggest something crude that abuses the 2^n bitshift relationship of 1 << n:

    int n = 7830457;
    BigInteger base = new BigInteger( "1" );
    BigInteger result = base.shiftLeft(n);

    and warn you it will take a long time to compute no matter how you optimize it. Then I read this:
    ... get the last 10 digits of that value
    Take a look at the modPow() function of BigInteger and consider how it can be used to take the modulo and compute the power together instead of doing them separately.

  5. #4
    Member
    Join Date
    Oct 2013
    Location
    Manila, Philippines
    Posts
    285
    My Mood
    Amused
    Thanks
    6
    Thanked 64 Times in 61 Posts

    Default Re: Seeking for better algo

    CampwideGames wrote
    Start with 2, 4, 8, 16, and so on, then when your number gets above ten digits just subtract off 10000000000, then double what you have left. The remaining ten digit number will be equal to the last ten digits of your final number. Program-wise you should be able to do it in a minute, no sweat.
    thank you sir it worked. but i did not check if the number exceeds 10 digits, i just mod it to 1000000000 everytime i double it, because i think checking the number using if-else statement will cost time. it execute less than a SECOND now, thank you for your help.

  6. #5
    Junior Member
    Join Date
    Dec 2013
    Posts
    2
    Thanks
    0
    Thanked 1 Time in 1 Post

    Default

    Glad to be of help!

Similar Threads

  1. Replies: 7
    Last Post: April 25th, 2013, 02:12 PM
  2. Algo for number systems (bin,hex,oct)
    By danskieness in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 7th, 2013, 10:27 PM
  3. seeking who will help
    By Zakariya Kumba in forum Member Introductions
    Replies: 0
    Last Post: November 9th, 2012, 09:29 PM
  4. [SOLVED] O(log n): a simple question for Logarithm in Data structures & Algo
    By chronoz13 in forum Algorithms & Recursion
    Replies: 1
    Last Post: September 7th, 2012, 09:20 AM
  5. Seeking help with a program.
    By Gravs2889 in forum What's Wrong With My Code?
    Replies: 3
    Last Post: March 15th, 2012, 08:51 AM