1. Home
  2. Embedded Programming
  3. continued fraction program

continued fraction program

Okay. I think I'm done playing, for now. There's a free continuous fraction program available. This program provides the convergents for the continuous fractions of a value (plus declining error terms) and includes a well-featured calculator (with variable assignment support and multi-statement capability (use a ; to separate statements or expressions, or just type them one line at a time) and displays floating point notation in either single or double precision (the calculator itself can be switched to either mode.) So it may have a variety of practical uses for folks in embedded work of one kind or another.

To keep it quick for me to develop and test (five hours of work, so far), I used VBDOS 1.0 as the compiler and it is developed to operate under DOS (obviously.) It works, so far as I'm aware, under the DOS boxes of various Windows incarnations. In order to avoid problems with sucking down CPU time while waiting for keystrokes (busy loop), the code also uses the DOS multiplex interrupt to release CPU time back to Windows during busy wait looping on keys. So it shouldn't do what many such DOS programs do when running under WinXP, for example, which is effectively hogging cpu time and presenting delays everywhere else on the machine.

The screen will auto-adjust to 50-line mode, if your DOS box otherwise starts up in other line modes, but will return back to the mode it starts in when it exits. Just be prepared for the 50-line display change, if you run it. Should also run under plain vanilla DOS systems, no Windows at all, so long as the video display supports the

50-line mode. That may be helpful with some PC104 systems.

It's free. Distribute it anyway you please. (It is offered basically "as is" and includes a non-transferable, non-exclusive, royalty-free worldwide license to use, copy, modify, prepare derivative works of, and distribute. More details are in the COPYRGHT.TXT file found in the ZIP that includes the .EXE file.)

The source code is also free for the asking on the same basis. But it will require at least QB4.5, 7.0, 7.1, or VBDOS to compile. It's in several modules but it's not hard to assemble the pieces into a QBASIC runnable version, though (I did it, just to be sure it works.) So that can be done successfully. (QBASIC is also free from Microsoft.)

It's at:

formatting link

Let me know if there are helpful improvements and I'll see what I can do.

Jon

Reply to
Jon Kirwan
Loading thread data ...

I learned about using continued fractions for gearing in machinery. For example if you need to cut metric screw threads in a lathe with an inch lead screw or vice versa. The exact conversion always requires a 127 tooth gear due to 127 mm = 5 inches. If you don't have a 127 tooth gear for the exact conversion, you can use continued fractions to see how close you can get to the metric pitch you need using the change gears that you have available.

Can your CF calculator be used for gear ratios like that? (Example: calculating a gear ratio that is close to 25.4 threads per inch from a screw with maybe 8 TPI)

RogerN

Reply to
RogerN

Yes. I think so. Here is the result for 25.4/8:

1: 3/1 -55,118.110 ppm 2: 16/5 7,874.016 ppm 3: 19/6 -2,624.672 ppm 4: 54/17 463.177 ppm 5: 73/23 -342.349 ppm 6: 127/40 exact

You tell me if that is what you were wondering about.

Jon

Reply to
Jon Kirwan

That's interesting. So, 127/5 = 25.400000....

I wonder if this has any significance to the chosen exact ratio of

25.4mm/inch ?

Bob

--
== All google group posts are automatically deleted due to spam ==
Reply to
BobW

Yes, 25.4 mm per inch would be 254mm per 10 inches but can be reduced to

127mm in 5 inches.

RogerN

Reply to
RogerN

Dang. That was too easy and obvious. I was hoping for something deeper. Oh well.

;-)

Bob

--
== All google group posts are automatically deleted due to spam ==
Reply to
BobW

Yeah, that looks like it would do it.

So if number 4: 54/17 was close enough the compound gearing might be something like:

Multiply the fraction to get compound gearing, I'm doubling here.

2* 2*3*3*3 2* 17 = 6 * 18 2 * 17

So my final gears might be

36:12 and 36:34

So I'd have, from spindle to lead screw, a 34 driving a 36 attached to a 12 driving a 36 on the lead screw.

RogerN

Reply to
RogerN

That doesn't appear to be what I call a continued fraction. It seems much closer to the following (which is purely standard C - will run anywhere):

/* Find best rational approximation to a double */ /* by C.B. Falconer, 2006-09-07. Released to public domain */

#include #include #include #include #include #include

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 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); if (0 == (int)approx) continue; 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 ratapprx 6.175 Usage: ratvalue [number [maxnumerator]] number defaults to PI, maxnumerator to 500 Rational approximation to 6.175000000000000 4 / 1 = 4.000000000000000 with error 2.175000000000000 5 / 1 = 5.000000000000000 with error 1.175000000000000 6 / 1 = 6.000000000000000 with error 0.175000000000000 19 / 3 = 6.333333333333333 with error 0.158333333333334 25 / 4 = 6.250000000000000 with error 0.075000000000000 31 / 5 = 6.200000000000000 with error 0.025000000000000 37 / 6 = 6.166666666666667 with error 0.008333333333333 68 / 11 = 6.181818181818182 with error 0.006818181818182 105 / 17 = 6.176470588235294 with error 0.001470588235294 142 / 23 = 6.173913043478261 with error 0.001086956521739 247 / 40 = 6.175000000000000 with error 0.000000000000000

which indicates some errors in your program to me, or a misunderstanding.

--
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: 
            Try the download section.
Reply to
CBFalconer

Neat, writing and giving away programs.

I just a minute ago finished a PowerBasic (Console Compiler) program that prowls my parts database looking for pairs of resistors that can hit a desired ratio (tolerance specified) and Thevenin range. It allows me to include 0603, 0805, or 1206 resistors in any combination.

It outputs a file that lists all the pairs, actual ratio, ratio error, and actual parallel (Thevenin) value, followed by a 1-line inventory report for each. The output file looks like...

RUGRAT Resistor ratio report 06-20-2009 17:35:18

Target ratio 2.500000 Accuracy limit 1.000 per cent Thevenin 500.000 to 2,000.000 Types : 0805

Ratio 2.517483 Error 0.699 pct Thevenin 511.730

132-5250 RES 0805 1.8K 5% DIGIKEY P1.8KACT-ND 0.01 4226 11671 132-4821 RES 0805 715R 1% DIGIKEY RHM715CCT-ND 0.02 196 11104

Ratio 2.481390 Error -0.744 pct Thevenin 574.483

132-5291 RES 0805 2K 1% DIGIKEY P2.00KCCT-ND 0.01 5348 11759 132-4871 RES 0805 1/8W 806R 1% KOA RK73H2A8060F 0.01 515 11777

Ratio 2.481390 Error -0.744 pct Thevenin 574.483

132-5291 RES 0805 2K 1% DIGIKEY P2.00KCCT-ND 0.01 5348 11759 132-4872 RES 0805 806R 0.1% MOUSER 71-TNPW0805806RBE 0.64 79 11597

Ratio 2.481390 Error -0.744 pct Thevenin 574.483

132-5292 RES 0805 2K 0.1% MOUSER 71-TNPW08052K00BE 0.64 81 11596 132-4871 RES 0805 1/8W 806R 1% KOA RK73H2A8060F 0.01 515 11777

etc, 32 solutions in this case, several perfect hits. The parts lines are long, so wrap when pasted to the newsgroup.

This is about 400 lines of code, took about 2 hours to do, although I'll probably spend another hour to check, beautify, and comment everything. The PBCC compiler allows real SLEEP commands, so I use them to keep the cpu from being hogged when nothing's going on.

I included a spiffy progress bar for when it's doing the file input and crunching, which turned out to be silly since it runs in about half a second. The search is a brute-force nested FOR loop.

This is free too, but it needs an input file that includes one line per resistor in stock, in our format, so some futzing would be needed for general use. Our material control system MAX makes this text file automatically every time it's run, so I used that instead of opening the binary record file.

Oh, it's packed with GOTOs.

John

Reply to
John Larkin

... snip ...

My earlier answer was almost accurate, but I ran my program with the wrong input. Try:

[1] c:\c\ratapprx>ratapprx 3.175 Usage: ratvalue [number [maxnumerator]] number defaults to PI, maxnumerator to 500 Rational approximation to 3.175000000000000 2 / 1 = 2.000000000000000 with error 1.175000000000000 3 / 1 = 3.000000000000000 with error 0.175000000000000 10 / 3 = 3.333333333333333 with error 0.158333333333334 13 / 4 = 3.250000000000000 with error 0.075000000000000 16 / 5 = 3.200000000000000 with error 0.025000000000000 19 / 6 = 3.166666666666667 with error 0.008333333333333 35 / 11 = 3.181818181818182 with error 0.006818181818182 54 / 17 = 3.176470588235294 with error 0.001470588235294 73 / 23 = 3.173913043478261 with error 0.001086956521739 127 / 40 = 3.175000000000000 with error 0.000000000000000

So my comment about errors is nonsense.

--
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: 
            Try the download section.
Reply to
CBFalconer

25.4/8 is 3.175.

John

Reply to
John Larkin

No problem. By the way, I only provide convergents. Just keep that in mind. The CF for 3.175 is [3;5,1,2,1,1]. This means exactly 6 convergents. Which is what you saw me post.

Jon

Reply to
Jon Kirwan

By the way, that program ALSO is a calculator program. In includes a few predefined values, like PI and E, but also all of the usual math functions like SIN, COS, COSH, EXP, LN, LOG, ABS, COTH, SQRT, and you name it. You can enter numbers, expressions, assignment statements, access the prior answer as part of the next formula, enter FP numbers in pure HEX format, use CF expressions such as [2;1,1,1]+[0;2,2,2] and get a return of [3;11,1] as your CF, which is 8/3+5/12 = 37/12.

Thought I'd get the point across that it doesn't just accept simple numbers. You can enter SQRT(7) and immediately see that it is the CF of [2;1,1,1,4,1,1,1,4,1,1,1,4,...] Just saying...

Jon

Reply to
Jon Kirwan

"Close" is not good enough; the Jameco cabinet mounting plate for 19" racks (PN 149500) now come with screws; i think they are made in China on Metric lathes. The screws look OK even against US ones, but they will not fit; forcing them will result in a virtual single piece of rack rail plus useless screw. And Jameco refuses to acknowledge the problem - much less fix it.

Reply to
Robert Baer

Don't you need a lot of food for the GOATs?

Reply to
Robert Baer

You'll find 127-tooth gears in many thread-cutting metalworking lathes.

Best regards, Spehro Pefhany

--
"it's the network..."                          "The Journey is the reward"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com
Reply to
Spehro Pefhany

For 25.4/8 the screen looks something like:

Actually, I use DOS drawing characters on the screen but you get the idea. Floating point is called out, as well.

The simple help message from ? is:

Jon

Reply to
Jon Kirwan

I thought it would be neat to write a program to calculate gear ratios and use exact and ratios from continued fractions. I wanted to enter the gears I had available in a table and see if I could get a program to select the gears for the correct ratio.

But then I got a lathe with quick change gears and now I have a CNC lathe that runs from EMC in Linux (linuxcnc.org). If I want to cut 10.123 threads per inch, no problem.

RogerN

Reply to
RogerN

I don't know what you mean by 'convergents' or 'CF'. ratapprx reports every value that reduces the error from the previous trial. Note the continuous reduction in error. Errors are absolute values.

--
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: 
            Try the download section.
Reply to
CBFalconer

CF (continued fraction) and convergent, if you look it up, is explicitly defined. See Wiki:

formatting link

I think another term for it is approximant.

I list the sign of the relative error as to some people that may be an important consideration. They can freely ignore the sign, if they want to. It's not so easy to "put the sign back" if it isn't stated in the listing.

Jon

Reply to
Jon Kirwan

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.