Member Avatar for peter26

I've gotten this question for an assignment in our introduction to computer science. And I have absolutely no idea on how to solve it. Help very much appreciated!!
This may sound like a cliché, but my girlfriend just left me, so I can't think straight even though how hard I try, and I have to deliver this by tommorow..

Question:
Design an algorithm for finding the cubic root of a positive integer,
rounded down to the nearest integer. Thus, given input N, a positive
integer, you should find a positive integer m such m^3 is smaller or equal to N, but (m + 1)^3 > N. Use the binary search idea.

(a) Express the algorithm in pseudocode.
(b) Find a fundamental operation and use big theta notation to ex-
press how long your algorithm takes. Express this as a function
of the positive integer N which is input, and also as a function of
the length of N (the number of bits in N). State any assumption
you make about how long it takes to multiply two integers, one of
length s and one of length t.

  • 2 Contributors
  • 1 Reply
  • 97 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Momerath
Member Avatar for Momerath

This is the same problem as the "guess the number" game. You pick a range to search in that you know the number (in this case, the cube root) exists. You then divide this range in half, and determine which half the number exists in. Repeat dividing in half until you have the number you are searching for.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.