I think it might be an intersting problem.
To solve it without using fpu, just interger instructions and without brutforce.
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);endfunctionfunction y=g(x,n)	y = 2^n;endfunctionx=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));endforplot(hor,ver);``
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	retr123:	adc eax,ecx	cmp edx,2	adc eax,ecx	cmp edx,1	adc eax,ecx	err:	retx_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