| Author |
Message |
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
 Posted: 16 Nov 2005 03:38:39 pm Post subject: |
|
|
[EDIT – 6/20/2008] – Stop referencing the program in this post. The one here is better.
I was writing a program to convert quadratic equations into the form (a±b√c)/d and then simplify the numerator/denominator by pulling out the greatest common factor, but I became hesitant to use [font="courier new"]gcd()—I knew that with this action, I would no longer be able use decimals in the fraction. So, I looked into Wolfram for an alternative, and found exactly what I was looking for: a method to calculate the greatest common divisor of two numbers, decimal or not.
As I continued feeding numbers into the machine for the sake of trial-and-error, it started to become more and more transparent that the inverse of each decimal result simply turned out to be a whole number. My eyes shot wide open as I realized the implications of this masterful approach to revealing the smallest possible integer into which each decimal would then multiply to yield, gracefully, another whole number.
Here is the algorithm:
[font="courier new"]Ans→X
abs(Ans
{max(Ans,1),min(Ans,1
Repeat E‾9>Ans(2
{Ans(2),Ans(1)-Ans(2)int(Ans(1)/Ans(2
End
1/Ans(1
int({AnsX,abs(Ans
The error argument is tentative; this inherently implies that the algorithm is not flawless, but it is still by far the most productive of all my previous experiments with fractions. I had some fun manipulating this variable to return some familiar results. For example, it is well known among number theorists that the fourth root of 2143/22 is almost equal to pi. So, I increased the error allowance to 10^-4 and ran through an input of pi^4. My result, as expected, was 2143/22. :)
Bottom line is, now we can take an ugly decimal like -1.3427625 and convert it into a nice fraction like -107421/80000 (with 0 residual left over). Did I mention that it's fast? The previous instance takes almost no time at all! And the best part is, any input is just as fast. :biggrin:
[font="courier new"]Ans for the win! \o/
Last edited by Guest on 20 Jun 2008 04:50:15 am; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 16 Nov 2005 05:44:53 pm Post subject: |
|
|
Words cannot describe how wonderful this is. May I have your permission to put this up on my website (giving you full credit, of course)?
Some small optimization, which in no way detracts from your accomplishments:
[font="courier new"]Ans→X
abs(X
{max(Ans,1),min(Ans,1
Repeat E‾9>Ans(2
Ans(2){1,fPart(Ans(1)/Ans(2
End
1/Ans(1
int({AnsX,abs(Ans
This implies that Ans(1) after exiting from the loop is equal to
b*fPart(a/ *fPart(1/fPart(a/)*fPart(1/fPart(1/fPart(a,b )))*...'
if a and b are the two parts of the list when entering the loop. If only one could do recursion in a seq( statement, this would be easy to calculate; as it is, not so easy. I'm still not sure I completely understand how this method works.
This is... beautiful.
Edit: there seems to be some sign trouble once in a while though, I think it's from the int(. If you change it to round( it works perfectly.
Last edited by Guest on 16 Nov 2005 07:37:06 pm; edited 1 time in total |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 16 Nov 2005 08:06:20 pm Post subject: |
|
|
Certainly, you can put it up on your website. I'll keep that optimization handy, too. Boy, I was simply astounded that something like this could be implemented so feasibly! It was a notoriously long-term problem, but I think that it may have passed... Honestly, sitting in class one period after sending the post, I had to check my calculator once or twice to see if it really happened. :)
Quote: So, I increased the error allowance... Heh, I could not for the life of me remember the term "tolerance" as I was writing this.
To clarify the algorithm, the result of m modulo n becomes n and the previous n becomes m. This continues until the result is null, and the previous n (now m) is the greatest common divisor/denominator/factor of the original values for m and n. Well, that's the run-down, but I don't have a real explanation as to how it all works out. 
Last edited by Guest on 16 Nov 2005 08:08:18 pm; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 16 Nov 2005 08:25:19 pm Post subject: |
|
|
Supergoose wrote: To clarify the algorithm, the result of m modulo n becomes n and the previous n becomes m. This continues until the result is null, and the previous n (now m) is the greatest common divisor/denominator/factor of the original values for m and n.[post="61651"]<{POST_SNAPBACK}>[/post] Which is Euclid's algorithm for GCD. *headdesk* I feel stupid now.
[font="courier new"]Ans→X
abs(X
{max(Ans,1),min(Ans,1
Repeat E‾9>Ans(2
Ans(2){1,fPart(Ans(1)/Ans(2
End
round({X,1}/Ans(1),0
This is the version I'm putting up. I was thinking of some clever optimization that involved storing the numbers as a complex number, but it never worked out.
Edit: is there really any reason for the numbers to start out ordered? If they're not, it simply adds another iteration in which it essentially switches them. I think the speed difference is sufficiently slight to ignore it in exchange for size:
[font="courier new"]Ans→X
{1,abs(X
Repeat E‾9>Ans(2
Ans(2){1,fPart(Ans(1)/Ans(2
End
round({X,1}/Ans(1),0
Last edited by Guest on 16 Nov 2005 08:35:02 pm; edited 1 time in total |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 16 Nov 2005 08:28:31 pm Post subject: |
|
|
[font="courier new"]Ans→X
abs(Ans
…
I'm working on how this can be applied to prime searches now. 8)
[EDIT]
It doesn't work correctly for -1.3427625 anymore. This error begins in the first optimization.
Last edited by Guest on 16 Nov 2005 09:08:53 pm; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 16 Nov 2005 09:22:01 pm Post subject: |
|
|
| Works well for positive numbers, so it's just a sign problem we'll have to fix. |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 17 Nov 2005 05:56:54 am Post subject: |
|
|
Very nice, the Euclidean algorithm is known to be an ancient and efficient algorithm. Anyone writing books on algorithms would hang his/her head in shame if they overlook this. So don't feel too bad, DarkerLine. :)
I have in my calculator the extended Euclidean algorithm used for calculating the so-called extended GCD:
Code:
Program:EGCD
:Prompt A, B
:{1,0}→S:{0,1}→U
:Repeat not(B)
:int(A/B)→Q
:A-QB→R
:B→A:R→B
:∟S-Q∟U→W
:∟U→S:∟W→U
:End
:DelVar ∟U
:DelVar ∟W
:Disp ∟S
:Disp "GCD=":A
Optimize as you please. :D
I'm currently working on writing a similar algorithm for polynomial GCD. :)
thornahawk
P.S. Among other things, this can be used for implementing modular exponentiation, a very useful operation in cryptography.  |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 18 Nov 2005 08:58:52 pm Post subject: |
|
|
[font="courier new"]Ans→X
{1,abs(X
Repeat E‾9>Ans(2
Ans(2){1,fPart(Ans(1)/Ans(2
End
iPart({X,1}/Ans(1
I can't prove mathematically that this works the same, but haven't been able to find an example in which it doesn't. I hate rounding. |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 30 Dec 2005 03:56:26 am Post subject: |
|
|
In the course of a recent library raid I conducted, I came upon an interesting article and was reminded of this thread. I present the algorithm discussed in the paper:
Code:
PROGRAM:DE2FR
Input "NO.? ",W
10^5→M \\ maximum expected denominator; tweak as seen fit;)
(2M²–M)ֿ¹→E
W→V
{0,1→L:{1,0→M
1→Q
While Q
int(Vֿ¹)→R
sum({R,1}∟L)→N
sum({R,1}∟M)→D
augment({N},∟L)→L
augment({D},∟M)→M
2→dim(∟L)
2→dim(∟M)
(abs(W–N/D)≥E)→Q
If Q
Vֿ¹–R→V
End
{N,D \\numerator and denominator
As mentioned in the paper, the algorithm as written works only for numbers in the open interval (0, 1) , although it should be trivial to modify the algorithm for numbers outside the range.
I'm also attaching the paper for the details.
thornahawk |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 30 Dec 2005 04:21:31 am Post subject: |
|
|
This offers very generous results, but I'm a bit upset at the continual crashing due to dividing by zero.
I see the code tested on the Amdahl 470, and will try to work out a neater adaptation. |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 30 Dec 2005 04:35:14 am Post subject: |
|
|
For what input(s) did the "divide by zero" error occur? I already mentioned that the code will fail for numbers not between 0 and 1 unless modified (only then is the error expected). Could you elaborate?
thornahawk |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 30 Dec 2005 05:29:31 am Post subject: |
|
|
It was my fault. After the short time I spent typing it out, I forgot the one
limitation you mentioned and didn't think to look back at the post for any.
The previously-addressed modification can go like this:
[font="courier new"]Input "NO.? ",W
iPart(W→I
fPart(W→W
…
End
{DI+N,D
This is effective! Another great breakthrough for TI-83+ fraction
conversions, and quite possibly the last one we'll ever need. 
Last edited by Guest on 30 Dec 2005 08:53:45 pm; edited 1 time in total |
|
| Back to top |
|
|
elfprince13
Retired
Super Elite (Last Title)
Joined: 11 Apr 2005
Posts: 3500
|
| Posted: 30 Dec 2005 09:26:59 am Post subject: |
|
|
| beasty! I've wasted many a class period coming up with crappy programs of this sort that didn't work.... |
|
| Back to top |
|
|
koresho
Advanced Newbie
Joined: 24 Mar 2006
Posts: 53
|
| Posted: 20 Apr 2006 03:29:24 pm Post subject: |
|
|
ok, so ket e get this straight...
to convert decimal to fraction, all you do is store the decimal as X then
Code:
{1,abs(X
Repeat E‾9>Ans(2
Ans(2){1,fPart(Ans(1)/Ans(2
End
iPart({X,1}/Ans(1
? is that it? then display X?
thanks... |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 21 Apr 2006 10:58:02 am Post subject: |
|
|
Actually, DE2FR, with Goose's modification, would do a better job. :P
thornahawk |
|
| Back to top |
|
|
koresho
Advanced Newbie
Joined: 24 Mar 2006
Posts: 53
|
| Posted: 21 Apr 2006 11:59:59 am Post subject: |
|
|
| so then, I use Goose's modification, and just put it in? |
|
| Back to top |
|
|
programmer_to_be
Jesus is my Lord and Saviour.
Elite
Joined: 07 Feb 2006
Posts: 755
|
| Posted: 21 Apr 2006 06:35:41 pm Post subject: |
|
|
| Yep. That code should work. |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 01 Aug 2006 04:58:03 am Post subject: |
|
|
Ans→X
While fPart(Ans
10Ans
End
round(Ans{1,X‾¹},0
Ans/gcd(abs(Ans(1)),Ans(2
At 48 bytes, this program quickly† translates a number (positive or negative) into fraction form iff both the numerator and denominator of the unsimplified (pre-gcd()) result are less than E12, so this is limited in that any input with more than a certain number of digits (usually around 11) or with any kind of repeating decimal fails. For example, 1/3 = 0.333… (or a non-integer multiple thereof) will return ERR:DOMAIN because the unsimplified form is registered as 333…333/100…000. Both parts of this fraction would consist only of fourteen digits because of the way the calculator handles numbers, but gcd() won't accept values that large.
Obviously, other numbers that it won't work with are: [font="times new roman"]π, e, √(2), ln(2), etc. A remedy is to prefix your input with round(, which will reduce the accuracy only slightly. Also, take a look at √(6)². At a glance, we can already tell that it has a finite number of decimals (namely, 6.0), but the calculator's imperfect storage methods will tell us otherwise. So, it crashes when it's not supposed to. You should use round( in this case to get a reasonable (often perfectly accurate) answer. Another anomalous example is writing out 1/3, multiplying it by 3 as a second operation, and then running the result through the program.
†It finishes in less than half a second on my TI-84+SE, no matter the input.
A few examples:
.51448:prgmA
____{6431 12500}
‾.020983648:prgmA
{‾655739 31250000}
Ans(1)/Ans(2
_____‾.020983648
round(e²:prgmA
{7389056099 1000000000}
e²-Ans(1)/Ans(2
_______‾6.96E‾11
–Goose
[EDIT]
This (faster) variation forgives the number of digits preceeding the decimal point of the input, allowing you to use much larger numbers in the integer part while keeping the same amount of digits in the fraction part. The same rules apply regarding long strings of numbers after the decimal point, except when the integer part is large enough so that the fraction part is truncated during storage anyway.
Ans→X
Ans/abs(Ans→S
iPart(X→Y
abs(fPart(X
E11{Ans,1
Ans/gcd(Ans(1),Ans(2
{SAns(1)+YAns(2),Ans(2
I'm open to new concepts.
Last edited by Guest on 23 Sep 2010 11:34:41 pm; edited 1 time in total |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 01 May 2007 11:06:18 pm Post subject: |
|
|
With the recent set of posts in this topic, I decided to take another look at the DE2FR code I posted earlier in this topic, and modify it by reimplementing the recursions inherent in the algorithm as matrix multiplications. Thus:
Code:
PROGRAM:DE2FR
Input "NO.? ",W
10^5→M \\ maximum expected denominator; tweak as seen fit;)
(2M²–M)ֿ¹→E
identity(2)→[F]
iPart(W)→I
W–I→F:F→V:1→Q
While Q
Vֿ¹→H:int(H)→R
[F][[0,1][1,R]]→[F]
[F](1,1)→N
[F](2,1)→D
(abs(F–N/D)≥E)→Q
If Q:H–R→V
End
DelVar [F]
N+ID→N:{N,D} \\numerator and denominator
The program now incorporates the modification to handle numbers outside the (0,1) interval.
(edit 10/1/2007: I changed the link following the creation of the TI-Basic Brain Teasers forum.)
thornahawk
Last edited by Guest on 01 Oct 2007 02:46:15 am; edited 1 time in total |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 08 Oct 2007 07:17:04 pm Post subject: |
|
|
Ans→A
{1,0→A
abs(A→B
0
Repeat not(A-Ans‾¹round(AnsA,0
{Ans,Ansint(B)+LA(1→A
If fPart(B
1/fPart(B→B
max(LA
End
round(Ans{A,1 // See posts further down for explanation
All inputs accepted, positive or negative, with absolutely zero error across the board; not even a E‾14.
[EDIT] – Saved four more bytes.
Last edited by Guest on 23 Sep 2010 11:32:05 pm; edited 1 time in total |
|
| Back to top |
|
|
|
TI-Basic => TI-BASIC
