News:

MASM32 SDK Description, downloads and other helpful links
MASM32.com New Forum Link
masmforum WebSite

min(n) & X*n^2<2^n

Started by The Svin, April 03, 2006, 07:08:33 PM

Previous topic - Next topic

The Svin

I think it might be intersting short solving task for asm. progrmmers since it brings attention to log2.
To make it more intersting I suggest write code using only integer part of CPU.
If the problem is not clear:
n > 0 & 0 >x>232
n & x belong to Z (intergers)
x is an argument to your proc (variable)
with given x your proc should find min(n) that meets condition x*n2<2n
This task can be easily done with brutforce (n cicles) or with table, wich is not interesting.
Number of "scan" cicles can be much less than n.
Eoin, suggested that brutforce could be appropriate. I was surprized :)
Hint:
At least there are many ways to see from wich n the scan can be started (starting with 1 in most cases just waste of  lots of time)
I offer the task since many abilities of x86 codes can be succesfully applied to the task.

Eóin

In my defence I suggested brute force because you can only search for n's in the range 1 to 32, whereas the pseudo binary search I used in the matlab script could in theory have performed 64 comparasions in the worst case (assuming you stuck to ints which I didn't) :bg .

The Svin

OK let's make the first little step:
What if know that MSB of x (wich is [lg x] - square br. mean here integer part of expression) for example equal 7?
(can be done with bsr instruction for example)
Would you still start search n from 1?