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*n

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*n

^{2}<2^{n}For positive X the minimum N is 0:

x * 0

x * (-1)

For negative X the minimum N is close to negative infinity, beacuse anything

if x > 0 then n = 0

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

However, the result of 2

So, the code will be:

x * 0

^{2}< 2^{0}x * (-1)

^{2}> 2^{-1}For negative X the minimum N is close to negative infinity, beacuse anything

^{2}is positive, multiplied by a negative number becomes negative. 2^{anything}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 2^{n}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

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);

OK. n > 0

For positive X the minimum N is 0

Let n > 0.? To make the problem easyer to formalize in x86 coding

Let 0<X<2

^{32}& X,n belong to Z.

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++]

TheSvin left this community of his own accord. Someone else will have to pick-up the basis of this conversation.

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.

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)

How very interesting. Thanks for the link.