Algorithms: Assume that each word of your machine has 64 bits....

[miamia]

Hello, I am currently working on HW for my algorithms class and I am stuck on how to approach the problem. Any advice would be appreciated. Right now I am still stuck on part a.

1. Assume that each word of your machine has 64 bits. Assume that you can multiply two n-word numbers in time 3n² with a standard algorithm. Assume that you can multiply two n-word numbers in time 8n^lg3 with a “fancy” algorithm. For each part briefly justify and show your work.

(a) Approximately, how large does n have to be for the fancy algorithm to be better?
(b) How many bits is that?
(c) How many decimal digits is that?

note: in this class we treat lg as log base 2

I think I am supposed to do something along the lines of 3n² <= 8n^lg3 and solve for n, but I do not know how to do that...

Thank you

 

[Harry_the_cat]

Hello, I am currently working on HW for my algorithms class and I am stuck on how to approach the problem. Any advice would be appreciated. Right now I am still stuck on part a.

1. Assume that each word of your machine has 64 bits. Assume that you can multiply two n-word numbers in time 3n² with a standard algorithm. Assume that you can multiply two n-word numbers in time 8n^lg3 with a “fancy” algorithm. For each part briefly justify and show your work.

(a) Approximately, how large does n have to be for the fancy algorithm to be better?
(b) How many bits is that?
(c) How many decimal digits is that?

note: in this class we treat lg as log base 2

I think I am supposed to do something along the lines of 3n² <= 8n^lg3 and solve for n, but I do not know how to do that...

Thank you

If "better" means shorter time then you want to find when 8n^lg3 <= 3n²

log₂3 = 1.58496...

So you want to find the smallest n for which 8n^1.58496... <= 3n²

Does that help?