Calculating n with Super-Fast Computing: P1-P4

[blackle]

• P1 takes n days to run
• P2 takes n^2 days to run
• P3 takes 2^n days to run
• P4 takes log(n) in base 2 days to run
So, to run P2 on an n of 4 would take 16 days.

a. For each version of the program, calculate the value of n (rounded down) we could compute if we let the program run for 12 billion years , which is (very) roughly how long until the Earth’s sun dies.

b. Let’s say we have access to a computer which runs one million times faster than the one above; so we could compute P1(1) in one millionth of a day. Write out the n we could compute for each of the above algorithms given this new processing power.

The Attempt at a Solution

a) I believe I solved part a) correctly.
P1: n = 12 000 000 000
P2: n = SquareRoot(12 000 000 000)
P3: n = log(12 000 000 000) in base 2
P4: n = 2^12 000 000 000

b) I have been trying to grasp the problem. So what values are we exactly supposed to find?
I understand:
P1: n = 1 took 1 day. but processor is 1 million times faster so takes 1/1000000 days.

What I am confused about is what of P2 are we supposed to calculate?
P2: n = 1 took 1 day. - do we take n to be 1? or we calculate the value of n to run an algorithm for 1/1000000 days like we did in part a)?

Any help would be appreciated. Thanks!

 

[Mark44]

• P1 takes n days to run
• P2 takes n^2 days to run
• P3 takes 2^n days to run
• P4 takes log(n) in base 2 days to run
So, to run P2 on an n of 4 would take 16 days.

a. For each version of the program, calculate the value of n (rounded down) we could compute if we let the program run for 12 billion years , which is (very) roughly how long until the Earth’s sun dies.

b. Let’s say we have access to a computer which runs one million times faster than the one above; so we could compute P1(1) in one millionth of a day. Write out the n we could compute for each of the above algorithms given this new processing power.

The Attempt at a Solution

a) I believe I solved part a) correctly.
P1: n = 12 000 000 000
P2: n = SquareRoot(12 000 000 000)
P3: n = log(12 000 000 000) in base 2
P4: n = 2^12 000 000 000

b) I have been trying to grasp the problem. So what values are we exactly supposed to find?
I understand:
P1: n = 1 took 1 day. but processor is 1 million times faster so takes 1/1000000 days.

What I am confused about is what of P2 are we supposed to calculate?
P2: n = 1 took 1 day. - do we take n to be 1? or we calculate the value of n to run an algorithm for 1/1000000 days like we did in part a)?

Any help would be appreciated. Thanks!

If I understand the problem correctly, if P1 runs for 12,000,000,000 years, n would not be 12,000,000,000 (which is in years); n would be 12,000,000,000 years x 365 days/year. This mistake affects all of your answers.

For the b part, if P1 takes n = 12,000,000,000 x 365 days, then on the faster computer P1 would take 12,000,000,000 x 365 /1,000,000 days, or 12,000 X 365 days. And so on for P2, P3, and P4.

 

[SammyS]

• P1 takes n days to run
• P2 takes n^2 days to run
• P3 takes 2^n days to run
• P4 takes log(n) in base 2 days to run
So, to run P2 on an n of 4 would take 16 days.

a. For each version of the program, calculate the value of n (rounded down) we could compute if we let the program run for 12 billion years , which is (very) roughly how long until the Earth’s sun dies.

b. Let’s say we have access to a computer which runs one million times faster than the one above; so we could compute P1(1) in one millionth of a day. Write out the n we could compute for each of the above algorithms given this new processing power.

The Attempt at a Solution

a) I believe I solved part a) correctly.
P1: n = 12 000 000 000
P2: n = SquareRoot(12 000 000 000)
P3: n = log(12 000 000 000) in base 2
P4: n = 2^12 000 000 000

b) I have been trying to grasp the problem. So what values are we exactly supposed to find?
I understand:
P1: n = 1 took 1 day. but processor is 1 million times faster so takes 1/1000000 days.

What I am confused about is what of P2 are we supposed to calculate?
P2: n = 1 took 1 day. - do we take n to be 1? or we calculate the value of n to run an algorithm for 1/1000000 days like we did in part a)?

Any help would be appreciated. Thanks!

The problem statement is a bit confusing. For part (a), I take it to mean that:

Algorithm P1 takes n days to calculate n - or maybe n things.
Algorithm P2 takes n² days to calculate n.
Algorithm P3 takes log₂(n) days to calculate n.
Algorithm P4 takes 2ⁿ days to calculate n.​

There are on average, about 365.24 days per year, so there are approximately 365.24 (days/year)·12×10⁹years ≈ 4.38×10¹² days in 12 billion years.

It looks like you should compute each answer; in other words,

rather than saying that for P2: n = √(4.38×10¹²),
you should say that for P2: n = 2.09×10⁶,
etc.​

For part (b):

This computer is 1 million times as fast, so Algorithm P1 takes n/1,000,000 days to calculate n - or maybe n things. Equivalently, Algorithm P1 takes n days to calculate n million. You could also think of this as follows: The fast computer can calculate in 12×10⁹years what the slow computer (in part a) would require 12×10¹⁵ years to calculate.

The following may be handy for getting some of your results log₂(x)=(1/ln(2))·ln(x) or log₂(x)=(1/log₁₀(2))·log₁₀(x).

For instance, in part (a), P3 can calculate n = log₂(4.38×10¹²) = (1/log₁₀(2))·log₁₀(4.38×10¹²) ≈ (3.3219)·[log₁₀(4.38)+log₁₀(10¹²)] = (3.3219)·[log₁₀(4.38)+ 12]. Notice that log₁₀(10^k) = k

FYI: The Earth's sun has only about 5 billion years left - before burning out.

 

[blackle]

Thanks everyone for the reply, especially Sammy :)

 

[Mark44]

Both SammyS and I were confused about what the problem was saying, especially this part: "calculate the value of n (rounded down) we could compute...". If this is the exact wording of the problem, you should probably get clarification on what it means from your instructor.

Computers don't generally compute a number; they perform an operation or a sequence of operations that results in a number.