3

In a Project Euler problem I need to deal with numbers that can have hundreds of digits. And I need to perform some calculation on the first 9 digits.

My question is: what is the fastest possible way to determine the first N digits of a 100-digit integer? Last N digits are easy with modulo/remainder. For the first digits I can apply modulo 100 times to get digit by digit, or I can convert the number to String and truncate, but they all are linear time. Is there a better way?

Konrad Garus
  • 53,145
  • 43
  • 157
  • 230
  • 2
    most project Euler solutions have "a ha!" solutions as well as 'brute force'...Also, your question is not programming related – Mitch Wheat Dec 24 '10 at 08:25
  • why converting the number to String and doing str[i] is linear ? –  Dec 24 '10 at 12:58
  • 2
    @Mitch: How exactly is this question "not programming related"? – bendin Dec 28 '10 at 18:00
  • nice question from someone with ~10k. Can you provide more details: how integer is represented and how you want to use those 9 digits? Btw, seems that you are on the wrong way with your current solution is you require this. – max taldykin Nov 17 '12 at 12:00

4 Answers4

5

You can count number of digits with this function:

(defn dec-digit-count [n]
  (inc (if (zero? n) 0
  (long (Math/floor (Math/log10 n))))))

Now we know how many digits are there, and we want to leave only first 9. What we have to is divide the number with 10^(digits-9) or in Clojure:

(defn first-digits [number digits]
  (unchecked-divide number (int (Math/pow 10 digits))))

And call it like: (first-digits your-number 9) and I think it's in constant time. I'm only not sure about log10 implementation. But, it's sure a lot faster that a modulo/loop solution.

Also, there's an even easier solution. You can simply copy&paste first 9 digits from the number.

Goran Jovic
  • 9,418
  • 3
  • 43
  • 75
3

Maybe you can use not a long number, but tupple of two numbers: [first-digits, last-digits]. Perform operations on both of them, each time truncating to the required length (twice of the condition, 9 your case) the first at the right and the second at the left. Like 

222000333 * 666000555
147|852344988184|815

222111333 * 666111555
147|950925407752|815

so you can do only two small calculations: 222 * 666 = 147[852] and 333 * 555 = [184]815

But the comment about "a ha" solution is the most relevant for Project Euler :)

zmila
  • 1,651
  • 1
  • 11
  • 13
1

In Java:

public class Main {
    public static void main(String[] args) throws IOException {
        long N = 7812938291232L;
        System.out.println(N / (int) (Math.pow(10, Math.floor(Math.log10(N)) - 8)));
        N = 1234567890;
        System.out.println(N / (int) (Math.pow(10, Math.floor(Math.log10(N)) - 8)));
        N = 1000000000;
        System.out.println(N / (int) (Math.pow(10, Math.floor(Math.log10(N)) - 8)));
    }
}

yields

781293829
123456789
100000000
Victor Sorokin
  • 11,878
  • 2
  • 35
  • 51
0

It may helps you first n digits of an exponentiation

and the answer of from this question

This algorithm has a compexity of O(b). But it is easy to change it to get O(log b)

Community
  • 1
  • 1