The program calculates the continued fraction representation of the input:
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char* argv[])
{
double diff, n, r, i;
if(argc != 2) exit(EXIT_FAILU RE);
n = strtod(argv[1], NULL);
printf("\n [");
while(1)
{
i = (int)n;
printf(" %.f", i);
diff = n - i;
r = 1 / diff;
if(r is a whole number) /* ??? */
{
printf(" %.f", r);
break;
}
n = r;
}
printf("]\n");
return 0;
}
In the while() loop, I want to test whether r is a whole number. If it
is, it is the last denominator of the continued fraction and I'm done.
Incredibly, I was not able to do this in any straighforward way. For
example, if(r == (int)r) didn't work. I finally kludged it by writing a
function that counts the significant decimal digits in a real number,
but there has got to be a better way. How would you solve the problem?
(And, yes, I realize that if the input is irrational the program doesn't
terminate.)
David 3 9908
In article <xNGxe.148629$E l.135738@pd7tw1 no>,
David Marsh <dm****@mail.co m> wrote: The program calculates the continued fraction representation of the input:
r = 1 / diff; if(r is a whole number) /* ??? */
In the while() loop, I want to test whether r is a whole number. If it is, it is the last denominator of the continued fraction and I'm done. Incredibly, I was not able to do this in any straighforward way. For example, if(r == (int)r) didn't work. I finally kludged it by writing a function that counts the significant decimal digits in a real number, but there has got to be a better way. How would you solve the problem?
You don't. Your entire sequence is subject to increasing round-off
error. Even if r -appeared- to be a whole number, you wouldn't
be able to tell whether you had calculated the exact continued
fraction, or had instead merely ended up rounding off to that
value.
The algorithm you are using to calculate the continued fraction
only works when there is indefinite precision.
Consider, for example, something as simple as the input
value (double) 1.0 / (double) 3.0 . No matter how many bits
of precision you have, if you are using a binary representation
then you have the binary repeating fraction 01 (i.e.,
1/3 is binary 0.0101010101... ) That is [using fraction notation]
1/4 + 1/16 + 1/64 + 1/256 + 1/1024 + 1/4096 + ...
and after 2N mantisa bits, your value is different from 1/3 by
the value 1/(3 * 2**(2N)).
If you expand this logic, then because of limited precision
on input, then even if you didn't lose precision during
the calculation, only the fractions which are sums of
negative powers of 2 are going to come out properly,
and *every* fraction that involves a prime greater than 2
would merely come out expressed in terms of negative
powers of 2, to the limit of the number of mantisa bits.
So... you cannot do any meaningful accurate continued-fraction
calculation with the algorithm you give.
The closest you can get is to lose a bit of precision,
understand that wrong answers will be given sometimes,
and change the "if" to check to see whether r is within
a tolerance of a whole number. For example,
if(r is a whole number) /* ??? */
would become something like
if ( abs(r - trunc(r)) < delta )
and you get to choose the delta according to how much slop you
are willing to put up with.
--
"This was a Golden Age, a time of high adventure, rich living and
hard dying... but nobody thought so." -- Alfred Bester, TSMD
David Marsh wrote: The program calculates the continued fraction representation of the input:
In the while() loop, I want to test whether r is a whole number. If it is, it is the last denominator of the continued fraction and I'm done. Incredibly, I was not able to do this in any straighforward way. For example, if(r == (int)r) didn't work. I finally kludged it by writing a function that counts the significant decimal digits in a real number, but there has got to be a better way. How would you solve the problem?
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>
#define ALMOST_ZERO (1.e-10)
#define MAXV 20
int main(int argc, char *argv[])
{
double thenumber, copy;
double denominator[MAXV], n, d, t;
int pass;
if (argc != 2) {
fprintf(stderr, "usage: %s number\n", argv[0]);
exit(EXIT_FAILU RE);
}
thenumber = strtod(argv[1], 0);
if (thenumber < 0) {
printf("changin g sign of %.f\n", thenumber);
thenumber *= -1;
}
printf("[ ");
for (copy = thenumber, pass = 0; pass < 20; pass++) {
copy = modf(copy, &denominator[pass]);
printf("%.f ", denominator[pass]);
if (copy < ALMOST_ZERO)
break;
copy = 1. / copy;
}
printf("]\n");
if (pass == 20)
pass--;
if (pass == 0) {
n = denominator[0];
d = 1;
}
else {
for (n = 1, d = denominator[pass], pass--; pass > 0; pass--) {
t = d * denominator[pass] + n;
n = d;
d = t;
}
n += d * denominator[0];
}
printf("%.f/%.f = %.*g\n"
" the original number was %.*g\n", n, d, DBL_DIG,
n / d, DBL_DIG, thenumber);
return 0;
}
Walter Roberson wrote: You don't. Your entire sequence is subject to increasing round-off error. Even if r -appeared- to be a whole number, you wouldn't be able to tell whether you had calculated the exact continued fraction, or had instead merely ended up rounding off to that value.
The algorithm you are using to calculate the continued fraction only works when there is indefinite precision.
So... you cannot do any meaningful accurate continued-fraction calculation with the algorithm you give.
The closest you can get is to lose a bit of precision, understand that wrong answers will be given sometimes, and change the "if" to check to see whether r is within a tolerance of a whole number. For example,
OK, I think I understand the precision issue. The source of the
algorithm (and everything I know about continued fractions) is: http://en.wikipedia.org/wiki/Continued_fraction (Calculating continued
fraction representations ).
Martin Ambuhl's program uses the fudge factor approach. I compared the
output of his program with mine. In every case my output was comparable
to his. Some examples below:
input David's program Martin's program
---------------------------------------------
..3 0;3,3 0;3,2,1
..5 0;2 0;2
..75 0;1,3 0;1,3
..829 0;1,4,1,5,1,1,2 ,1,3 0;1,4,1,5,1,1,2 ,1,3
..999 0;1,999 0;1,998,1
Anyway, it has become a discussion of algorithms and CS, not standard C,
so it's off-topic here. Thanks for your comments. BTW, are you Canadian?
David This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Edvard Majakari |
last post by:
Hi,
I just found py.test and converted a large unit test module to py.test
format (which is actually almost-no-format-at-all, but I won't get there
now). Having 348 test cases in the module and huge test classes, I started
to think about splitting classes. Basically you have at least three obvious
choises, if you are going for consistency in your test modules:
Choise a:
|
by: Billy Patton |
last post by:
I have worked out a testing procedure that works well for me.
Here it is for your taking. It has evolved over 15 years of
c and perl coding and testing. My perl version looks VERY similar.
It actually came for need to do something else besides what the perl test
modules offered. Some lines are too long for Pine and it puts them on seperate
line, so you will have to rebuild some of the #defines.
int nr = 0; /* total number...
|
by: Sisyphus |
last post by:
Hi,
I have some software that does the following (in an attempt to determine
whether the double x, can be represented just as accurately by a float):
void test_it(double x) {
float y = x;
if(x == y) {
printf("x can be represented precisely by a float\n");
}
|
by: Jacob |
last post by:
I have compiled a set og unit testing
recommendations based on my own experience
on the concept.
Feedback and suggestions for improvements
are appreciated:
http://geosoft.no/development/unittesting.html
Thanks.
|
by: brad |
last post by:
Does anyone else feel that unittesting is too much work? Not in general,
just the official unittest module for small to medium sized projects?
It seems easier to write some quick methods that are used when needed
rather than building a program with integrated unittesting. I see the
value of it (the official unittest that is)... especially when there's a
lot of source code. But this...
if len(x) != y:
sys.exit('...')
| |
by: yogi_bear_79 |
last post by:
I have a double of unknown length that I need to split at the
decimal. I thought I would convert it either to a string or a char.
char seems to be the best since it easily lends itself to splitting.
I have a few issues with this theory. Hard codeing char M works
fine for my test double -0.5 But I would like it to be more
versitile. The format "%2.2f" works fine with my test data, but that
should also be versitile.
inline void...
|
by: David |
last post by:
Hi list.
What strategies do you use to ensure correctness of new code?
Specifically, if you've just written 100 new lines of Python code, then:
1) How do you test the new code?
2) How do you ensure that the code will work correctly in the future?
Short version:
|
by: VK |
last post by:
In the continuation of the discussion at "Making Site Opaque -- This
Strategy Feasible?" and my comment at
http://groups.google.com/group/comp.lang.javascript/msg/b515a4408680e8e2
I have realized that despite suggestions to use DHTML-based modal
dialogs are very common? there is not a single fully functional
reliable copyright-free cross-browser alternative to say MsgBox
(VBScript) or showModalDialog (IE). This way such suggestions up to...
|
by: scienceman88 |
last post by:
I'm making a prime finder another thing I'd like is a loop to check all possible odd factors if I can do that i can find all primes under 18 quintillion I think and store them in files ( yes I have nearly 200 GB of space left). also thanks for the thread on finding position in a file it helped me stop the file getting to big too open in MS-DOS
//---------------------------------------------------------------------------
#include <stdlib.h>...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
| |
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |