如何编写有关此问题的最有效代码？ [英] How can I write the most efficient code about this problem?
问题描述
最近，我有兴趣编写非常有效的代码。
问题：
有一个序列{a（0），a（ 1），...，a（n-1）}和一个非常小的
正整数k，写一个算法而不使用乘法来计算
计算下面的公式：
n-1
_____
\
\ ki
/ 2 * a（i）
/ _____
i = 0
我的答案如下：
inline int sum（int a []，size_t n，size_t k）{
int sum = 0;
while（n--）（sum << = k）+ = a [n];
返还金额;
}
请指点如果我的答案是最好的答案？
您能否列出您的答案？谢谢！
Gerald
Recently, I''m interested in writing very efficient code.
Problem:
there is a sequence { a(0), a(1), ..., a(n-1) } and a very small
positive integer k, write an algorithm without using multiply to
calculate the following formula:
n-1
_____
\
\ ki
/ 2 * a(i)
/_____
i = 0
My answer is following:
inline int sum(int a[], size_t n, size_t k) {
int sum = 0;
while (n--) (sum <<= k) += a[n];
return sum;
}
would you please point out if my answer is the best answer?
And could you cite out your answer? Thank you!
Gerald
推荐答案
我不是数学家，但我有doutbs你的代码会工作。
我认为2 ^ k可以在总和之前进行分解，所以它应该看起来像
（+总和定义（作为代码数组）从0 ... n-1）
inline int sum（int a []，size_t n，size_t k）{
int sum = 0;
while（n）sum + = a [n--];
返回总和<< k;
}
问候，Viktor
Hi,
I am not mathematician but I have doutbs your code will work.
I think 2^k can be factorised before the sum, so it should look like
(+ sum is defined (as code array) from 0...n-1)
inline int sum(int a[], size_t n, size_t k) {
int sum = 0;
while (n) sum += a[n--];
return sum << k;
}
Regards, Viktor
我的代码绝对正确，至少在VC6。也许你没有理解这个问题。系数2是k * i，而不是k。
请你再试一次吗？谢谢！
问候，Gerald
My code is absolutely correct, at least at VC6. Maybe you didn''t
understand the problem. The coefficient of 2 is k * i, not k.
Would you please try it again? Thank you!
Regards, Gerald
st ********* @ gmail.com 写道：
st*********@gmail.com wrote:
最近，我很感兴趣编写非常有效的代码。
问题：
有一个序列{a（0），a（1），...，a（n-1）}和一个非常小的
正整数k，写一个算法而不用乘法来计算下面的公式：
n-1
_____
\
\ ki
/ 2 * a（i）
/ _____
我= 0
我的答案如下：
inline int sum（int a [ ]，size_t n，size_t k）{
int sum = 0;
while（n--）（sum<< = k）+ = a [n];
返回和;
}
如果我的答案是最佳答案，请指出？
我认为，它非常接近：你正在使用Horner方案来评估
多项式，并且你实现乘以2的幂乘以位
换班。我看到的唯一浪费的指令是一个冗余的初始位
在已知为0的点上移动总和。可能，编译器
可以优化它。
但是，请记住，如果不参考
a特定平台，效率很难争论。另一方面，平台特定的问题在这个组中关闭了
主题。
您能否列出您的答案？
Recently, I''m interested in writing very efficient code.
Problem:
there is a sequence { a(0), a(1), ..., a(n-1) } and a very small
positive integer k, write an algorithm without using multiply to
calculate the following formula:
n-1
_____
\
\ ki
/ 2 * a(i)
/_____
i = 0
My answer is following:
inline int sum(int a[], size_t n, size_t k) {
int sum = 0;
while (n--) (sum <<= k) += a[n];
return sum;
}
would you please point out if my answer is the best answer?
I think, it is pretty close: you are using the Horner scheme to evaluate the
polynomial, and you realize multiplication by powers of 2 by means of bit
shifting. The only wasted instruction that I see is a redundant initial bit
shift of sum at a point where it is known to be 0. Probably, the compiler
can optimize that away.
Keep in mind, however, that efficiency is hard to argue without reference to
a specific platform. On the other hand, platform specific questions are off
topic in this group.
And could you cite out your answer?
嗯？
最好
Kai-Uwe Bux
Huh?
Best
Kai-Uwe Bux
这篇关于如何编写有关此问题的最有效代码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
