I think it might be an intersting problem.
To solve it without using fpu, just interger instructions and without brutforce.
If task is not clear:
x - is some integer var (argument to a proc).
The task is to find a minimum integer n that meets condition:
x*n2<2n
Posted on 2006-04-01 22:42:43 by The Svin
For positive X the minimum N is 0:

x * 02 < 20
x * (-1)2 > 2-1

For negative X the minimum N is close to negative infinity, beacuse anything2 is positive, multiplied by a negative number becomes negative. 2anything is always positive. Hence, the left side (negative) will always be less then the right side (positive). So, in 32-bit integer arithmetics:

if x > 0 then n = 0
if x <= 0 then n = -2147483648 (0x80000000)

However, the result of 2-2147483648 is not an integer value, but this was not the rule of the task (only x and n were supposed to be integers), but if the result of 2n should be integer too, then the smallest integer n that meets the condition would be 0.

So, the code will be:

  xor eax, eax
  test x, 80000000
  setne al
  ror eax,1
Posted on 2006-04-02 08:14:02 by Morris
For some reason I was intrigued by what a graph plotting n against x would look like for x*n^2 = 2^n. I knocked together a quick octave script to work it out and thought I'd post it.

clear all;

function y=f(x,n)
y = x*(n^2);
endfunction

function y=g(x,n)
y = 2^n;
endfunction

x=1;

for z=1:200

x=x+1000;
n=1;
step=0.5;

while f(x,n) >= g(x,n)
n=n*2;
step=step*2;
endwhile

while step >= 0.00001
if f(x,n) >= g(x,n)
n=n+step;
else
n=n-step;
endif

step=step/2;
endwhile

hor(z)=x;
ver(z)=n;

# printf("x=%5.2f n=%5.2f f=%5.2f g=%5.2f\r\n",x,n,f(x,n),g(x,n));
endfor

plot(hor,ver);
Attachments:
Posted on 2006-04-02 09:54:43 by Eóin
OK. n > 0
Posted on 2006-04-02 11:27:07 by The Svin

For positive X the minimum N is 0

Let n > 0.?  To make the problem easyer to formalize in x86 coding
Let 0<X<232 & X,n belong to Z.
Posted on 2006-04-02 18:36:51 by The Svin
is this ok?

x_n_n_lt_2_n proc X
xor ecx,ecx
mov edx,X
xor eax,eax
cmp edx,2234634
ja err
cmp edx,3
jc r123
.data
__nval equ <6,10,16,28,48,83,145,256,453,809,\
?  ?  ?  ?  ?  ?  1452,2621,4755,8665,15857,29127,53687,\
?  ?  ?  ?  ?  ?  99273,184112,342392,638372,1193046,2234634>
.code
dec ecx
mov eax,8
%for n,<__nval>
cmp edx,n
sbb eax,ecx
endm
ret
r123:
adc eax,ecx
cmp edx,2
adc eax,ecx
cmp edx,1
adc eax,ecx
err:
ret
x_n_n_lt_2_n endp

For]; n++]
Posted on 2006-04-03 07:14:07 by drizz
TheSvin left this community of his own accord. Someone else will have to pick-up the basis of this conversation.
Posted on 2006-04-03 07:18:01 by SpooK
I would think that seeing as the graph I plotted shows n growing in a log fashion that a brute force search would actually be quite a valid technique.
Posted on 2006-04-03 10:28:13 by Eóin

I would think that seeing as the graph I plotted shows n growing in a log fashion that a brute force search would actually be quite a valid technique.


In fact it is a Lambert W function. http://mathworld.wolfram.com/LambertW-Function.html

If you solve it for n then you get:

-2*lambertw(-1/2*log(2)/p^(1/2))/log(2) or -2*lambertw(1/2*log(2)/p^(1/2))/log(2)
Posted on 2006-04-07 08:22:29 by mr.schyte
How very interesting. Thanks for the link.
Posted on 2006-04-07 09:29:49 by Eóin