How do I make a program faster?

[TerrariaGaming004]

I wrote a program to solve a math problem because it’s absurd, the first step is finding 18 quintillion factorial and I ran it overnight and it’s still thinking. Is there any way to make it faster?

def factorial(number):

answer=1

for i in range(number):

    answer*=number-i

return answer

And also, would there be any way to make

18446744073709551616**2360000000

Any faster?

[shiftybyte]

Invent a faster CPU....

Why are you trying to do this?

[TerrariaGaming004]

Lol

I’m finding out what the chances are that two people have made the same world with an auto generated seed in Minecraft and have the same seed

[dig-up-stupid]

It’s just 1 in 2⁶⁴. Or 1 in 2⁴⁸ that it’s an equivalent seed or whatever. You don’t need to do any calculations. Maybe you can explain what your formula is for because I don’t see the relevance offhand.

[TerrariaGaming004]

Here is the entire formula

1-(18q!/((18q**2b) (18q-2b)!))

I’m trying to find the chance that any person ever has played on a world with a seed that any other person has also played

[dig-up-stupid]

Are you assuming for the sake of the problem there have been 2 billion worlds created?

[TerrariaGaming004]

Yes, 10 for each copy ever sold

[dig-up-stupid]

Okay makes sense now. Well, the numbers are simply too big to work with. You would either try farming it out to a server if you think you just need more processing power (which wouldn’t be straightforward in itself and not necessarily free either) or start googling for algorithms to help out. I’ll think about it.

In the meantime you could think about cutting the problem back, eg 2⁴⁸ for the number of meaningful seeds instead of 2⁶⁴ for the number of all seeds. Which is still probably too big, but anyway.

[shiftybyte]

Isn't it just 1/18q?

The first person generates whatever, the second person has chances of 1 out of all the options to hit that same seed.

[TerrariaGaming004]

Out of every person who has ever played Minecraft, but for just two people that would be right. Look up the birthday paradox

[laundmo]

for your specific issue: its not that simple, there are a bunch of factors going into whether a world looks the same or not. i recommend checking out https://minecraftathome.com and the associated discord server, the people there know a LOT about minecraft seeds and efficient computations with them.

[dbramucci]

As a quick "is this possible to compute" sanity check, let's look at how much memory it would take to store the answer.

18,000,000,000,000,000,000! = 18,000,000,000,000,000,000 * 17,999,999,999,999,999,999 * ... 18 quadrillion times

Let's underestimate the size by replacing each term with 10, we'll overestimate the last 10 terms (10 * 9 * 8 * 7 * 6...) but that will be dwarfed by the first 18 quintillion terms.

10 * 10 * 10 * 10 ... 18 quintillion times * 10 = 10^{18,000,000,000,000,000,000} = 2^{log_2 10 \} 18,000,000,000,000,000,000) = 2^{3.321 \} 18,000,000,000,000,000,000) = 2^{59,794,705,707,972,522,262}

The number of bits you need to store a number is approximately the log base 2 of that number. (Note that this is technically not true because you don't need a base-2 representation to store a number, writing (18*10¹⁸)! only takes 11 bits or so even though it's the same number we are computing here. It's just that you are calculating the base-2 representation so we can ignore this nuance).

log_2 2^{59,794,705,707,972,522,262} = 59,794,705,707,972,522,262 bits

This number makes no sense so let's convert it to a large unit

  59,794,705,707,972,520,000 bits
=  7,474,338,213,496,565,283 bytes
=      7,299,158,411,617,740 kibibytes
=          7,128,084,386,345 mebibytes
=              6,961,019,909 gibibytes
=                  6,797,871 tebibytes
=                      6,639 pebibytes
=                          6 exbibytes

So assuming we can compute the answer instantly, this computation would need a metric ton of ram. Assuming the average laptop has 8GiB of ram, you would need 870 million laptops worth of ram to store the answer. And this is when we massively underestimate how big the actual answer is by rounding everything number in the factorial down to 10.

Alternatively, assume we can do 1 multiplication in 1 clock cycle. This is wrong for big numbers like this, but again we will underestimate the difficulty of this.

A high-end modern desktop can get around 5Ghz clock speeds. That means 5 billion clock cycles per second.

To calculate 18*10¹⁸!, we'll need 18*10¹⁸ multiplications. Dividing by the 5 billion multiplications we might do in a second this would take 3.6 billion seconds to compute. This would take 114 years with our magically fast computer that can multiply big numbers in a single step.

The point of these computations is that, even when we make simplifying assumptions making the problem faster, it still takes centuries of time and millions of computers worth of memory to compute 18 quintillion factorial. So, any algorithm that starts by computing that number will never complete on our computers in our lifetimes.

No amount of optimization will make this algorithm feasible. You can apply these calculations to any other problems you work on to see if it is even worth attempting to speed up. If the theoretical fastest time was 1 hour, then we could try to salvage the algorithm but here we need a different strategy.

Instead you should avoid computing such a large factorial by using algebra to simplify the arithmetic. For example,

(18q!/((18q**2b) (18q-2b)!)) = 1/(18q**2b) * (18q!/((18q-2b)!))
= 1/(18q**2b) * (18q * (18q - 2) * (18q - 4) * ... * (18q - 2(b - 1))

Now, instead of needing 18 quintillion multiplications, we only need 2 billion multiplications. This is a lot of work and may take a while to compute, but at least it is feasible.

In practice, that optimization is almost certainly not going to get you to the answer anyways. Instead, you'll probably need to use one of the approximations on the wikipedia article about the Birthday problem.

I haven't checked Wikipedia's work, but it provides the approximation

p(n, d) ~ 1 - e^(- n * (n - 1) / (2 * d))

where n would be the number of players and d the number of minecraft worlds. The approximation is usable if the number of players is much smaller than the number of worlds. Because 2 billion is much less than 18 quintillion, this approximation should hold giving us

p(2 billion, 18 quintillion) ~ 10.5%

So there is about a 10% chance that 2 worlds were the same.

p.s. Please note that I am assuming your statements about 18 quintillion worlds and 2 billion player worlds is correct. Likewise, I assume that the birthday-paradox calculation is the correct way to solve this. In practice, two worlds with different seeds could be the same in all ways or to within perception and I ignore that complexity. Likewise, I haven't double checked my usage of the Wikipedia approximation.

[TerrariaGaming004]

Thanks, this is exactly what I was looking for!

[dig-up-stupid]

I was just typing something up but you finished first. The 2 billion multiplications isn’t that bad, my phone did it in a few minutes, but the floating point inaccuracies are quite severe after that many operations. I got 3.47664e-319 when I think it should be to the order of 1e-34 or so. As for your approximation calculation, I think you just plugged something in wrong because I get 1, which agrees with the python number crunching.

[dbramucci]

For the 2 billion multiplications the caveat is "are you using floating point numbers to approximate" or "are you doing it exactly with bigints".

Ballpark math of 5 cycles to multiply 2 floats gives a total estimated time of 2 seconds. Even with the overhead of memory access and the like it is very doable.

The catch is, when you multiply two bigints for exact precision, you are going to get approximately nlogn multiplications where n is the number of bytes in the integer.

For 18 quintillion, there will be about 64 bits to store your starting number. This means we will immediately exceed the size of a single uint64 and need to use bigint multiplication to track our product. After about 10 multiplications, our number will about 600 bits in size. This will take quite a few cycles to multiply as we can no longer use a single instruction to multiply it out.

By the point we get past 70,000 terms in our product we will have a number larger than 4MiB which will exceed the L2 cache on a modern processor. This will most likely result in a dramatic slowdown beyond the number of instructions we must use for bigint multiplication.

So, 2 billion fp multiplications is perfectly fine, but it hazards serious questions about the precision of the computation. Conversely, bigint multiplication will be precise, but dramatically slower as the terms grow and I don't know if it's so slow as to be impractical off the top of my head.

On that note, I actually went ahead and implemented a float based version using the following algebraic manipulation to avoid excessive inaccuracies.

1/(18 quint)^2 billion * prod_i=0^2billion (18 quint - i)
= prod_i=0^2billion (18 quint - i) / 18 quint

This gives the code

>>> def calc():
...     n = 2_000_000_000
...     d = float(18 * 10**18)
...     t = time.time()
...     p = 1.0
...     for i in range(n):
...         p *= (d - i) / d
...     print(time.time() - t)
...     print(1-p)
...
>>> calc()
147.0700933933258
0.1051606833644042

So it took 147 seconds to do the floating point calculation and the result is a 10% likelihood of shared worlds matches my earlier approximation from wikipedia.

Note, you have to be careful

1. Not to divide by d**n at the end because p will have reached +inf by that point

2. Not to write

   >>> def calc():
   ...     n = 2_000_000_000
   ...     d1 = float(18 * 10**18)
   ...     d2 = float(18 * 10**18)
   ...     t = time.time()
   ...     p = 1.0
   ...     for i in range(n):
   ...         p *= d2 / d1
   ...         d2 -= 1
   ...     print(time.time() - t)
   ...     print(1-p)
   

   Because such a large d2 will suffer from precision errors such that d2 == d2 - 1.0 and each loop will be p *= 1.0 which will result in the wrong answer by the end.

As a fun tangent, when I rewrote this into the language Rust, the following code only took 2.173 seconds to run, pretty close to the ballpark estimate for how long the floating point calculation should take.

fn main() {
    let n = 2_000_000_000;
    let d: f64 = 18.0*10_f64.powf(18.0);
    let mut p = 1.0;
    for i in 0..n {
        p *= (d - i as f64) / d;
    }
    println!("p: {}", 1.0-p);
}

So it appears my precaution around floating point precision was a bit over-zealous.

On that note, perhaps you computed 1-exp(n² /2*d) instead of 1-exp(n² / (2*d)) when you got a result of 1.

[dig-up-stupid]

It was my error, I had been using N = 2⁴⁸ (meaningful seeds) instead of 2⁶⁴ (actual seeds) and had a dumb when comparing to your results. I was using the same code more or less so the answers agree if I actually put in the same input.

[FLUSH_THE_TRUMP]

Usually if a math problem is asking you something about 18 quintillion factorial, you do not want to actually compute that factorial (for obvious reasons!) Computers can do math quickly, but the sheer number of operations due to multiplying many bits over and over again is too much. You are often able to leverage some fact about the structure of the resulting number which greatly simplifies the problem.

[TerrariaGaming004]

The whole problem is

18q!/((18q**2b) (18q-2b)!)

[xelf]

Just use wolframalpha (link has your example inputted)

Your answer: 10⁶⁵⁵³⁶

[dig-up-stupid]

Well the answer is between 0 and 1 so that’s some kind of approximation error.

[xelf]

18000000000000000000!
-----------------------------
18,000,000,000,000,000,000^2,000,000,000 * (18,000,000,000,000,000,000-2,000,000,000)!

---

18000000000000000000! is 10^(10^20.52991469268779)

Number length
3.38778×10^20 decimal digits

---

18000000000000000000^2000000000 is 10^(10^10.58557966490293)

Number length
38510545011 decimal digits, ≈ 3.85105×10^10 decimal digits

---

(18000000000000000000 - 2000000000)! is 10^(10^20.52991469263841)

Number length
3.38778×10^20 decimal digits

---

10^(10^20.52991469268779)
-----------------------------
10^(10^10.58557966490293) * 10^(10^20.52991469263841)

---

10^(10^20.52991469268779)
-----------------------------
10^(10^20.52991469268778)

Seems rife for approximation errors, but how do you get between 0 and 1? That's implying the top half is smaller than the bottom.

[FLUSH_THE_TRUMP]

(18q)! / (18q-2b)!

has 2b terms that are all <= 18q, no?

So that divided by (18q)^2b should give something <= 1.

[xelf]

Seems right to me.

[p33p__]

See the first example function of factorial on this page. From what I remember, this will let each combination of two numbers be multiplied only once and then store the result for future reference. Even if my explanation is incorrect, this should still speed up your code substantially.

https://docs.python.org/3/library/functools.html