avatar
w*x
1
Write a function that computes log2() using sqrt().
glassdoor上看到的, 有人会做不?
avatar
j*o
2
好像见过
log2(n)=log2( (sqrt(n))^2 ) =2 log2(sqrt(n))
不过这样子只能算整数
比如8的根号是2.。。这样子= =“

【在 w****x 的大作中提到】
: Write a function that computes log2() using sqrt().
: glassdoor上看到的, 有人会做不?

avatar
h*e
3
不知道这样子做行不:
When N>1, log2(N) = log2(sqrt(N)^2) = 2log2(sqrt(N)),N iterate直到abs(N-1)<=epsilon (给定的精度要求)
When N=1, log2(N) = 0
When 01的情况。
avatar
a*x
4
我觉得思路对头,可以用recursion来算
public static double log2(double x) {
if( x - 1 < epsilon ){
return (x-1)/ln2; //base case 泰勒级数
} else{
return log2( Math.sqrt(x) ) * 2; // recursion
}
printf( " %d ", x/2);
}
问题在于需要hard code 常数 ln2

好像见过
log2(n)=log2( (sqrt(n))^2 ) =2 log2(sqrt(n))
不过这样子只能算整数
比如8的根号是2.。。这样子= =“

【在 j*****o 的大作中提到】
: 好像见过
: log2(n)=log2( (sqrt(n))^2 ) =2 log2(sqrt(n))
: 不过这样子只能算整数
: 比如8的根号是2.。。这样子= =“

avatar
a*x
5
终止条件可能会有比较大的误差。。。

【在 h****e 的大作中提到】
: 不知道这样子做行不:
: When N>1, log2(N) = log2(sqrt(N)^2) = 2log2(sqrt(N)),N : iterate直到abs(N-1)<=epsilon (给定的精度要求)
: When N=1, log2(N) = 0
: When 01的情况。

avatar
r*e
6
would this method solve it? it's O(1) but not accurate, of course.
sqrt(n) = 2^{0.5xlogN}, base is 2.
cannot remember how to represent it in latex, have not
used it for too long.

【在 w****x 的大作中提到】
: Write a function that computes log2() using sqrt().
: glassdoor上看到的, 有人会做不?

avatar
l*c
7
a means is to find the log2(n) where n > 1. When n < 1, calculate log2(1/n);
1. find the most closed 2's multiples (small, large) to the n, upper value
and lower value are respectively times values to 2. //for example, if we
find values are 8 and 16, n is between 8 and 16, result is between 3~4.
2. we know log2(sprt(small*large)) = (log2(small)+log2(large))/2 = (upper
value + lower value)/2. // for example log2(13.31) = 3.5.
3.Check if n is larger or less then sprt(small*large). Then change the lower
bound/higher bound to this new value. And result is between new value~
previous upper value/ precious lower value~new value.
4.Iterate until the result's range is less than error.
avatar
s*3
8
这题bit manipulation,recursion精度太差。

【在 w****x 的大作中提到】
: Write a function that computes log2() using sqrt().
: glassdoor上看到的, 有人会做不?

avatar
f*e
9
let log2(x)=y
then x=2^y
let z=sqrt^(n)(x^b/2^d)=2^((by-d)/2^n),b,d是自选的正整数(when y>0),b非常大,
所以下面有个d来平衡,使不超过表示范围。
assuming y>0(y<0可类推), increase n, for sufficient large n, when t just be
gins to fall bellow 4, it satisfies:
1thus by-d的最高位是n,然后对by-d-2^n做类似计算。
最后epsilon = 1/b

【在 s******3 的大作中提到】
: 这题bit manipulation,recursion精度太差。
avatar
s*3
10
看不懂, 这种解法或许成立,但显然不是出题者的本意。

大,
be

【在 f*****e 的大作中提到】
: let log2(x)=y
: then x=2^y
: let z=sqrt^(n)(x^b/2^d)=2^((by-d)/2^n),b,d是自选的正整数(when y>0),b非常大,
: 所以下面有个d来平衡,使不超过表示范围。
: assuming y>0(y<0可类推), increase n, for sufficient large n, when t just be
: gins to fall bellow 4, it satisfies:
: 1: thus by-d的最高位是n,然后对by-d-2^n做类似计算。
: 最后epsilon = 1/b

avatar
f*e
11
出题者本意是啥?不过不用sqrt都可以得到近似解。

【在 s******3 的大作中提到】
: 看不懂, 这种解法或许成立,但显然不是出题者的本意。
:
: 大,
: be

avatar
s*3
12
面试题最主要应该简单直接吧 程序设计又不是考数学 clear code, reusable
code是基本原则吧
我的理解

【在 f*****e 的大作中提到】
: 出题者本意是啥?不过不用sqrt都可以得到近似解。
avatar
f*e
13
上面那个比较糙,
发个优化版的:
考虑x>=1,(if x<1,考虑1/x), e.g. let
x=2^y=2^(1011.10111),y用二进制表示
for i=100:-100
x=(x/2^(2^i)>=1)?(a[i]=1, x/2^(2^i)):(a[i]=0, x);

//算2^(2^(-1:-100))需要用到sqrt,算法总的基本思想就是一位一位的算y的位。
y=sum {i= -100 to 100} a[i]*2^i
python code:
import math
w = range(9,-80,-1)
s = 0
x = 59876
y = x
if(x<1): x=1/x
for i in w:
b = x/2**(2**i)
if b>=1:
s += 2**i
x = b
if(y>=1):
print(s)
print(math.log(y,2))
else:
print(-s)
print(math.log(y,2))

【在 s******3 的大作中提到】
: 看不懂, 这种解法或许成立,但显然不是出题者的本意。
:
: 大,
: be

avatar
w*x
14
Write a function that computes log2() using sqrt().
glassdoor上看到的, 有人会做不?
avatar
j*o
15
好像见过
log2(n)=log2( (sqrt(n))^2 ) =2 log2(sqrt(n))
不过这样子只能算整数
比如8的根号是2.。。这样子= =“

【在 w****x 的大作中提到】
: Write a function that computes log2() using sqrt().
: glassdoor上看到的, 有人会做不?

avatar
h*e
16
不知道这样子做行不:
When N>1, log2(N) = log2(sqrt(N)^2) = 2log2(sqrt(N)),N iterate直到abs(N-1)<=epsilon (给定的精度要求)
When N=1, log2(N) = 0
When 01的情况。
avatar
a*x
17
我觉得思路对头,可以用recursion来算
public static double log2(double x) {
if( x - 1 < epsilon ){
return (x-1)/ln2; //base case 泰勒级数
} else{
return log2( Math.sqrt(x) ) * 2; // recursion
}
printf( " %d ", x/2);
}
问题在于需要hard code 常数 ln2

好像见过
log2(n)=log2( (sqrt(n))^2 ) =2 log2(sqrt(n))
不过这样子只能算整数
比如8的根号是2.。。这样子= =“

【在 j*****o 的大作中提到】
: 好像见过
: log2(n)=log2( (sqrt(n))^2 ) =2 log2(sqrt(n))
: 不过这样子只能算整数
: 比如8的根号是2.。。这样子= =“

avatar
a*x
18
终止条件可能会有比较大的误差。。。

【在 h****e 的大作中提到】
: 不知道这样子做行不:
: When N>1, log2(N) = log2(sqrt(N)^2) = 2log2(sqrt(N)),N : iterate直到abs(N-1)<=epsilon (给定的精度要求)
: When N=1, log2(N) = 0
: When 01的情况。

avatar
r*e
19
would this method solve it? it's O(1) but not accurate, of course.
sqrt(n) = 2^{0.5xlogN}, base is 2.
cannot remember how to represent it in latex, have not
used it for too long.

【在 w****x 的大作中提到】
: Write a function that computes log2() using sqrt().
: glassdoor上看到的, 有人会做不?

avatar
l*c
20
a means is to find the log2(n) where n > 1. When n < 1, calculate log2(1/n);
1. find the most closed 2's multiples (small, large) to the n, upper value
and lower value are respectively times values to 2. //for example, if we
find values are 8 and 16, n is between 8 and 16, result is between 3~4.
2. we know log2(sprt(small*large)) = (log2(small)+log2(large))/2 = (upper
value + lower value)/2. // for example log2(13.31) = 3.5.
3.Check if n is larger or less then sprt(small*large). Then change the lower
bound/higher bound to this new value. And result is between new value~
previous upper value/ precious lower value~new value.
4.Iterate until the result's range is less than error.
avatar
s*3
21
这题bit manipulation,recursion精度太差。

【在 w****x 的大作中提到】
: Write a function that computes log2() using sqrt().
: glassdoor上看到的, 有人会做不?

avatar
f*e
22
let log2(x)=y
then x=2^y
let z=sqrt^(n)(x^b/2^d)=2^((by-d)/2^n),b,d是自选的正整数(when y>0),b非常大,
所以下面有个d来平衡,使不超过表示范围。
assuming y>0(y<0可类推), increase n, for sufficient large n, when t just be
gins to fall bellow 4, it satisfies:
1thus by-d的最高位是n,然后对by-d-2^n做类似计算。
最后epsilon = 1/b

【在 s******3 的大作中提到】
: 这题bit manipulation,recursion精度太差。
avatar
s*3
23
看不懂, 这种解法或许成立,但显然不是出题者的本意。

大,
be

【在 f*****e 的大作中提到】
: let log2(x)=y
: then x=2^y
: let z=sqrt^(n)(x^b/2^d)=2^((by-d)/2^n),b,d是自选的正整数(when y>0),b非常大,
: 所以下面有个d来平衡,使不超过表示范围。
: assuming y>0(y<0可类推), increase n, for sufficient large n, when t just be
: gins to fall bellow 4, it satisfies:
: 1: thus by-d的最高位是n,然后对by-d-2^n做类似计算。
: 最后epsilon = 1/b

avatar
f*e
24
出题者本意是啥?不过不用sqrt都可以得到近似解。

【在 s******3 的大作中提到】
: 看不懂, 这种解法或许成立,但显然不是出题者的本意。
:
: 大,
: be

avatar
s*3
25
面试题最主要应该简单直接吧 程序设计又不是考数学 clear code, reusable
code是基本原则吧
我的理解

【在 f*****e 的大作中提到】
: 出题者本意是啥?不过不用sqrt都可以得到近似解。
avatar
f*e
26
上面那个比较糙,
发个优化版的:
考虑x>=1,(if x<1,考虑1/x), e.g. let
x=2^y=2^(1011.10111),y用二进制表示
for i=100:-100
x=(x/2^(2^i)>=1)?(a[i]=1, x/2^(2^i)):(a[i]=0, x);

//算2^(2^(-1:-100))需要用到sqrt,算法总的基本思想就是一位一位的算y的位。
y=sum {i= -100 to 100} a[i]*2^i
python code:
import math
w = range(9,-80,-1)
s = 0
x = 59876
y = x
if(x<1): x=1/x
for i in w:
b = x/2**(2**i)
if b>=1:
s += 2**i
x = b
if(y>=1):
print(s)
print(math.log(y,2))
else:
print(-s)
print(math.log(y,2))
也可以把浮点数二进制表示里的指数部分先搞出来,然后对mantissa部分(1面方法,复杂度会进一步降低。

【在 s******3 的大作中提到】
: 看不懂, 这种解法或许成立,但显然不是出题者的本意。
:
: 大,
: be

avatar
w*t
27
this one works well:
http://stackoverflow.com/questions/5701023/finding-log2-using-s
我做了一点修改,以支持 <= 1的情况:
18 double Log2(double val)
19 {
20 assert(val > 0.0f);
21 if (val == 1.0f) return 0;
22 bool neg_sign = false;
23 if (val < 1.0f) {
24 neg_sign = true;
25 val = 1.0f / val;
26 }
27 int hix = 0;
28 while((1<29 int lox = hix - 1;
30 double lval = (1<31 double rval = (1<32 double dlow = lox, dhigh = hix;
33 // while(fabs(lval - val) > 1e-7) {
34 while(dhigh - dlow > 1e-7) {
35 double mid = (dlow + dhigh) / 2;
36 double midValue = sqrt(lval*rval);
37
38 if (midValue > val) {
39 dhigh = mid;
40 rval = midValue;
41 } else {
42 dlow = mid;
43 lval = midValue;
44 }
45 }
46 return neg_sign ? -dlow : dlow;
47 }
>>>>>>> results:
Log2(1) = 0
Log2(2) = 1
Log2(3) = 1.58496
Log2(4) = 2
Log2(5) = 2.32193
Log2(6) = 2.58496
Log2(7) = 2.80735
Log2(8) = 3
Log2(9) = 3.16992
Log2(10) = 3.32193
Log2(11) = 3.45943
Log2(12) = 3.58496
Log2(13) = 3.70044
Log2(14) = 3.80735
Log2(15) = 3.90689
Log2(16) = 4
Log2(0.1) = -3.32193
Log2(0.2) = -2.32193
Log2(0.3) = -1.73697
Log2(0.4) = -1.32193
Log2(0.5) = -1
Log2(0.6) = -0.736966
Log2(0.7) = -0.514573
Log2(0.8) = -0.321928
Log2(0.9) = -0.152003
avatar
i*t
28
假设x是input, 大于1
我的方法(算指数的2进制表示):
double x=134.56,bit=0,z=0.5,epsilon=1.0000001,k=sqrt(2),r;
r=x;

// scale r to [1,2]

while (r>2){
r=r/2;
bit+=1;
}
// r is in [1,2]
while(r>epsilon){
if(r/k>1){
bit+=z;
r=r/k;
}
k=sqrt(k);
z=z/2;
}

【在 w****x 的大作中提到】
: Write a function that computes log2() using sqrt().
: glassdoor上看到的, 有人会做不?

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。