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
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
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:
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
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<232 & 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.