理性近似 [英] Rational approximations
问题描述
这是一个有趣的玩具，对于使用有理分数来表示实数的
Forthians可能特别感兴趣。
标准的处理也可能是有些人感兴趣。
/ *通过CB Falconer，2006-09-07找到最合理的近似值* /
/ *。发布到公共领域* /
#include< stdio.h>
#include< stdlib.h>
#include< math.h>
#include< float.h>
#include< limits.h>
#include < errno.h>
int main（int argc，char ** argv）
{
int num，approx ，bestnum，bestdenom;
int lastnum = 500;
双重错误，leasterr，value，criterion，tmp;
char * eptr;
value = 4 * atan（1.0）;
if（argc 2）lastnum = strtol（argv [2]，NULL，10）;
if（lastnum< = 0）lastnum = 500;
if（argc 1）{
tmp = strtod（argv [1]，& eptr）;
if（（0.0> = tmp）||（tmp INT_MAX）||（ERANGE == errno））{
puts（" Invalid number ，使用PI"）;
}
else value = tmp;
}
criterion = 2 * value * DBL_EPSILON;
puts（" Usage：ratvalue [num ber [maxnumerator]] \ n"
" number默认为PI，maxnumerator为500"）;
printf（" Rational approximation to％。* f\\ \\ n"，DBL_DIG，value）;
for（leasterr = value，num = 1; num< lastnum; num ++）{
约=（int）（num / value + 0.5）;
error = fabs（（double）num / approx - value）;
if（错误< leasterr）{
bestnum = num;
bestdenom =约;
leasterr = error;
printf（"％8d /％-8d =％。* f，错误％。* f \ n"，
bestnum，bestdenom，
DBL_DIG，（double）bestnum / bestdenom，
DBL_DIG，leasterr）;
if（leasterr< = standard）break;
}
}
返回0;
} / * main * /
-
Chuck F（cinefalconer at maineline dot net）
可用于咨询/临时嵌入式和系统。
< http://cbfalconer.home .att.net>
CBFalconer写道：
Here是一个有趣的玩具，对于使用有理分数来表示实数的
Forthians来说，这可能是特别感兴趣的。 br />
标准的处理也可能对某些人感兴趣。
/ *找到最合理的近似值* /
/ * CB Falconer，2006-09-07。发布到公共领域* /
实际上，双打已经是有理数。分母
总是2的幂。
现在它们的数字是近似的，这是一个不同的故事...
- Logan
CBFalconeraécrit：
这是一个有趣的玩具，可能特别感兴趣的是使用有理分数来表示实数的售后者。
标准的处理对某些人来说也可能很有意思。
/ *通过CB Falconer，2006-09-07找到最合理的近似值* /
/ *。发布到公共领域* /
#include< stdio.h>
#include< stdlib.h>
#include< math.h>
#include< float.h>
#include< limits.h>
#include < errno.h>
int main（int argc，char ** argv）
{
int num，approx ，bestnum，bestdenom;
int lastnum = 500;
双重错误，leasterr，value，criterion，tmp;
char * eptr;
value = 4 * atan（1.0）;
if（argc 2）lastnum = strtol（argv [2]，NULL，10）;
if（lastnum< = 0）lastnum = 500;
if（argc 1）{
tmp = strtod（argv [1]，& eptr）;
if（（0.0> = tmp）||（tmp INT_MAX）||（ERANGE == errno））{
puts（" Invalid number ，使用PI"）;
}
else value = tmp;
}
criterion = 2 * val ue * DBL_EPSILON;
puts（" Usage：ratvalue [number [maxnumerator]] \ n"
" number默认为PI，maxnumerator为500"）;
printf（" Rational approximation to％。* f\ n"，DBL_DIG，value）;
for（leasterr = value，num = 1; num< lastnum; num ++）{
约=（int）（num / value + 0.5）;
error = fabs（（double）num / approx - value）;
if（错误< leasterr）{
bestnum = num;
bestdenom =约;
leasterr = error;
printf（"％8d /％-8d =％。* f，错误％。* f \ n"，
bestnum，bestdenom，
DBL_DIG，（double）bestnum / bestdenom，
DBL_DIG，leasterr）;
if（leasterr< = standard）break;
}
}
返回0;
} / * main * /
对不起Chuck但我认为你在第一次迭代中调用UB
当我们有：
num = 1
value = PI
我们有：
1 / PI = 0.31830 ....
（int）0.31830 == ZERO
然后你做了
num / approx你有一个divis零离子...
jacob
CBFalconer写道：
< blockquote class =post_quotes>
/ *查找最合理的近似值* /
可以试着说他们解决了一个稍微不同的问题，
但是连续分数提供了最佳近似值，
易于编码，并产生令人着迷的结果，例如。
e = 2.71828 ... is { 2; 1,2,1,1,4,1,1,6,1,1,8,1,1,10，...]
继续分数形式，并且
黄金比例为[1; 1,1,1,1,1,1,1，...]。
（此cf黄金比率的形式意味着它是真实数字
最难接近理性！黄金比例
总线调度算法取决于属性IIRC，
虽然大多数comp-sci算法称为黄金比率
算法。不要。）
像往常一样，维基百科似乎提供了一个很好的讨论：
http://en.wikipedia.org/wiki/Continued_fraction
value = 4 * atan（1.0）;
不记得如何拼写M_PI，是吗？我也不能，虽然
我通常只拼写拼写：3.141592635897
James Dow Allen
Here is an amusing toy, which may be of especial interest to the
Forthians who use rational fractions to represent real numbers.
The handling of criterion may also be interesting to some.
/* Find best rational approximation to a double */
/* by C.B. Falconer, 2006-09-07. Released to public domain */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>
#include <limits.h>
#include <errno.h>
int main(int argc, char **argv)
{
int num, approx, bestnum, bestdenom;
int lastnum = 500;
double error, leasterr, value, criterion, tmp;
char *eptr;
value = 4 * atan(1.0);
if (argc 2) lastnum = strtol(argv[2], NULL, 10);
if (lastnum <= 0) lastnum = 500;
if (argc 1) {
tmp = strtod(argv[1], &eptr);
if ((0.0 >= tmp) || (tmp INT_MAX) || (ERANGE == errno)) {
puts("Invalid number, using PI");
}
else value = tmp;
}
criterion = 2 * value * DBL_EPSILON;
puts("Usage: ratvalue [number [maxnumerator]]\n"
"number defaults to PI, maxnumerator to 500");
printf("Rational approximation to %.*f\n", DBL_DIG, value);
for (leasterr = value, num = 1; num < lastnum; num++) {
approx = (int)(num / value + 0.5);
error = fabs((double)num / approx - value);
if (error < leasterr) {
bestnum = num;
bestdenom = approx;
leasterr = error;
printf("%8d / %-8d = %.*f with error %.*f\n",
bestnum, bestdenom,
DBL_DIG, (double)bestnum / bestdenom,
DBL_DIG, leasterr);
if (leasterr <= criterion) break;
}
}
return 0;
} /* main */
--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>
CBFalconer wrote:Here is an amusing toy, which may be of especial interest to the
Forthians who use rational fractions to represent real numbers.
The handling of criterion may also be interesting to some.
/* Find best rational approximation to a double */
/* by C.B. Falconer, 2006-09-07. Released to public domain */Actually, doubles are already rational numbers. The denominator
is always power of 2.
Now the numbers they approximate, that''s a different story...
- Logan
CBFalconer a écrit :Here is an amusing toy, which may be of especial interest to the
Forthians who use rational fractions to represent real numbers.
The handling of criterion may also be interesting to some.
/* Find best rational approximation to a double */
/* by C.B. Falconer, 2006-09-07. Released to public domain */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>
#include <limits.h>
#include <errno.h>
int main(int argc, char **argv)
{
int num, approx, bestnum, bestdenom;
int lastnum = 500;
double error, leasterr, value, criterion, tmp;
char *eptr;
value = 4 * atan(1.0);
if (argc 2) lastnum = strtol(argv[2], NULL, 10);
if (lastnum <= 0) lastnum = 500;
if (argc 1) {
tmp = strtod(argv[1], &eptr);
if ((0.0 >= tmp) || (tmp INT_MAX) || (ERANGE == errno)) {
puts("Invalid number, using PI");
}
else value = tmp;
}
criterion = 2 * value * DBL_EPSILON;
puts("Usage: ratvalue [number [maxnumerator]]\n"
"number defaults to PI, maxnumerator to 500");
printf("Rational approximation to %.*f\n", DBL_DIG, value);
for (leasterr = value, num = 1; num < lastnum; num++) {
approx = (int)(num / value + 0.5);
error = fabs((double)num / approx - value);
if (error < leasterr) {
bestnum = num;
bestdenom = approx;
leasterr = error;
printf("%8d / %-8d = %.*f with error %.*f\n",
bestnum, bestdenom,
DBL_DIG, (double)bestnum / bestdenom,
DBL_DIG, leasterr);
if (leasterr <= criterion) break;
}
}
return 0;
} /* main */
Excuse me Chuck but I think you invoke UB in the first iteration
when we have:
num = 1
value = PI
we have then:
1/PI = 0.31830 ....
(int) 0.31830 == ZERO
Then you do
num/approx and you have a division by zero...
jacob
CBFalconer wrote:/* Find best rational approximation to a double */One could try to argue they solve a slightly different problem,
but continued fractions provide optimal approximations, are
easy to code, and yield fascinating results, eg.
e = 2.71828... is {2;1,2,1,1,4,1,1,6,1,1,8,1,1,10,...] in
continued fraction form, and
the Golden Ratio is [1;1,1,1,1,1,1,1,...].
(This c.f. form of Golden Ratio means it is the real number
hardest to approximate by a rational! The Golden Ratio
bus scheduling algorithm depends on that property IIRC,
though most comp-sci algorithms called "Golden Ratio
algorithm" don''t.)
As is so often the case these days, Wikipedia seems to
offer a good discussion:
http://en.wikipedia.org/wiki/Continued_fraction
value = 4 * atan(1.0);Can''t remember how to spell M_PI, eh? Neither can I, though
I usually just spell it prosaically: 3.141592635897
James Dow Allen
这篇关于理性近似的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
