Jump to content

Recommended Posts

Nice! If I can find a way to use it then I will.

I really cannot contribute, as this is still  above me.

Spoiler

 

"If a vegetarian eats vegetables,What the heck does a humanitarian eat?"

"I hear voices in my head, but I ignore them and continue on killing."

"You have forced me to raise the indifference warning to beige, it's a beige alert people. As with all beige alerts please prepare to think about the possibility of caring."

An optimist says that giving someone power DOESN'T immediately turn them into a sadist. A pessimist says that giving someone power doesn't IMMEDIATELY turn them into a sadist.

 

 
Link to comment
Share on other sites

Thanks Draygoes, the idea is to keep the original information intact and basically do maths with whole numbers. This way absolute accuracy is pretty much guaranteed, even when the whole numbers form part of a fraction. I think it's useful for small closed systems which use a lot of calculation. Only at the end of a number of precise calculations should the result be converted back to a float. This is the best way to maintain accuracy throughout a long winded calculation - where small inacuracies will have a knock on effect.

Edited by czardas
Link to comment
Share on other sites

Update to first post. The internal function __Expand() was causing problems. Thanks to a suggestion by guinness, the modifications I made seem to be working correctly. I also added an example of multiplying two fractions together, so you can see how maths can be done using this (100% accurate) method. The method is what you might call 'Old School', but you shouldn't let that put you off: you might need to use something like this one day.

Edited by czardas
Link to comment
Share on other sites

I would have done it using greatest common divisor to convert a float number to a fraction. Nice approach czardas!  :thumbsup:

Br,

UEZ

Edited by UEZ

Please don't send me any personal message and ask for support! I will not reply!

Selection of finest graphical examples at Codepen.io

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

Link to comment
Share on other sites

Thanks UEZ, and you're absolutely right! I was looking into this today and it would be much faster. There's a good method for GCD / HCF, used by PheonixXL, which I tested for speed earlier. I wasn't fully aware of the method until this afternoon - although something about it seems vaguely familiar. I think it's often a good exercise to try and solve a problem yourself, but finding neat little shortcuts is always good.

The prime sieve method was part of an earlier script I wrote: I thought I might save time using the same code again. After the speed tests I have revised that opinion. I will try implementing GCD. :thumbsup:

Edited by czardas
Link to comment
Share on other sites

Code updated in the first post.

After a slight delay, I've changed the method to use GCD - the only serious approach really. Although the method I used earlier was sound in principle, further tests revealed hidden bugs which (I believe) had everything to do with implementation. Until I get to the bottom of this, I thought it best to remove the original code.

It seems that my assumption of 15 digit accuracy was incorrect, although I'm not entirely sure why at this moment in time. I have therefore limited the function to 14 digit input (for the time being), which seems to be working so far. I don't really see much need for such extreme fractions outside pure mathematics.

I'm convinced that I have seen this method of Euclid previously - maybe it's deja-vu. Anyway I needed further convincing that such a simple idea was even possible:

g = gcd(a, b) = gcd(b, r0) = gcd(r0, r1) = … = gcd(rN−2, rN−1) = rN−1 :blink:

 

http://en.wikipedia.org/wiki/Euclidean_algorithm#Proof_of_validity

Actually Euclid's proofs are very beautiful. :)


Incidentally: the forum's tagged content seems to disappear when logged in to the forum: guests can see it but members cannot. So here's the link to the UDF (by PheonixXL) where I found the GCD code. The UDF uses string representation of a fraction, as opposed to using an array containing two integers. >mathsEX UDF

Edited by czardas
Link to comment
Share on other sites

You might have fun trying the binary GCD variant and Knuth-Shönage. For those not too faint-hearted, I higly recommend the evaluation of the traditional euclidean algorithm discussed by Knuth in TAOCP vol 2.

Also the euclidean algorithm is important to music.

Disclaimer: I'm a big big big fan of the magic of the extended euclidean algorithm for too many reasons to expose here.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Link to comment
Share on other sites

The second link is a nice find and the article is well written. This area of music theory has fascinated me for years. I had an idea back in 1991 which involves a different solution to the tuning problem. Instead of using approximations (as is the case with equal temperament), it is possible to make small adjustments to pitch when needed (if the key changes). This is something that many musicians do already, but without necessarily knowing the maths or theory.

There are limitations to the musician's real-world approach, but nowadays computers should be able to circumvent some of these limitations (put simply) by designating pitch ranges to notes, and perhaps allowing a some drift in the frequency of the fundamental to accomodate the comma mentioned in the article. I call this idea 'Drifting Temperament', and there are several possible implementations that could be tested. Theoretically it should be possible to enhance music, making it sound richer and super vibrant. You might have to redesign speakers to cope with the extra sympathetic resonance though. ;)

Unfortunately AutoIt (alone) isn't capable of testing this. It would require fractional calculations converted to floating point pitch values. You can do the maths easily enough, but finding software that is capable of producing cents (100th of a semitone) seems to be an issue. I'm sure the hardware is up to the task. Anyway, one problem at a time hey!

Now back to the regular schedule - this was quite a digression.

BTW, this isn't the reason I created this function, but investigating the maths involved was indeed on the back of my mind. Coincidence perhaps! :)

Edited by czardas
Link to comment
Share on other sites

Total bugfix and library expansion in 1st post ==> _FractionAbs(), _FractionAdd(), _FractionCeiling(), _FractionDivide(), _FractionFloor(), _FractionMod(), _FractionMultiply(), _FractionSubtract(), _IsFraction(), _IsFractionNegative(), _Reciprocal(). I also introduced the value negative zero (0 / -1) ... all other values can be negative so why not? ;)

The fifteen digit limit has been restored, although it still cannot be 100% guaranteed that internal rounding adjustments won't cause small inacuracies in extreme cases. Obsticles encountered during development were caused by some perplexing anomalies idiosyncrasies:

;

; Nines anomaly
Local $iNines = 999999999999999
Nines($iNines)
MsgBox(0, "Hmm", $iNines) ; 1000000000000000 - What happened here?

Func Nines(ByRef $iNines)
    $iNines = Abs($iNines)
    $iNines = Int($iNines)
EndFunc

; Another Anomaly
Local $nFloat = 3.1416
While Not IsInt($nFloat)
    $nFloat *= 10
WEnd
MsgBox(0, "No worries!", $nFloat) ; 3.1416e+016 - I was expecting something a bit smaller.

;

Regardless of these (mostly circumvented) rare and sometimes insignificant anomalies idiosyncrasies, you can generally perform precision calculations with fractions which will be more accurate than if you were to use floats to do the same task.

Edit : function names missing underscore.

Edited by czardas
Link to comment
Share on other sites

Both examples are not anomalies: they are illustrations of our arithmetical mental world biaised towards decimal representation and its difficulty to fit actual maths.

For instance the first one (here called "nines") is a floating-point paraphrasing of:

1/3 = 0.33333333333333333333333...

1/3 = 0.33333333333333333333333...

1/3 = 0.33333333333333333333333...

----    --------------------------------------------

 1   = 0.99999999999999999999999...

In "pure" maths, the ellipsis are the crux matter (i.e. an infinite number of significant digits), but here we fold the "problem" into a non-infinite number of digits, somehow complexified by the binary representation used by IEEE754. The nature of the pseudo-issue is nonetheless similar.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Link to comment
Share on other sites

Both examples are not anomalies: they are illustrations of our arithmetical mental world biaised towards decimal representation and its difficulty to fit actual maths.

 

Perhaps not an anomaly to those who trust in the maxim that all things must have a cause. Actually I borrowed the phraseology. Dispite all of this, there has to be more going on beneath the surface because the same commands executed without passing the ByRef parameter to Nines() unexpectedly produces an expected result. :ermm:

:

Local $iNines = 999999999999999
$iNines = Abs($iNines)
$iNines = Int($iNines)
Msgbox(0, "As expected", $iNines) ; 999999999999999

;

Well it seems unusual to me at this moment in time - I wonder what's going on. Good comment about limitations of the decimal system BTW. :)

Edited by czardas
Link to comment
Share on other sites

Your last example produces 1000000000000000 for me running x86 or x64. Abs appears to return a Double for me on Windows 7.

If I posted any code, assume that code was written using the latest release version unless stated otherwise. Also, if it doesn't work on XP I can't help with that because I don't have access to XP, and I'm not going to.
Give a programmer the correct code and he can do his work for a day. Teach a programmer to debug and he can do his work for a lifetime - by Chirag Gude
How to ask questions the smart way!

I hereby grant any person the right to use any code I post, that I am the original author of, on the autoitscript.com forums, unless I've specifically stated otherwise in the code or the thread post. If you do use my code all I ask, as a courtesy, is to make note of where you got it from.

Back up and restore Windows user files _Array.au3 - Modified array functions that include support for 2D arrays.  -  ColorChooser - An add-on for SciTE that pops up a color dialog so you can select and paste a color code into a script.  -  Customizable Splashscreen GUI w/Progress Bar - Create a custom "splash screen" GUI with a progress bar and custom label.  -  _FileGetProperty - Retrieve the properties of a file  -  SciTE Toolbar - A toolbar demo for use with the SciTE editor  -  GUIRegisterMsg demo - Demo script to show how to use the Windows messages to interact with controls and your GUI.  -   Latin Square password generator

Link to comment
Share on other sites

Thanks for testing it. I tested it on XP SP3 (x86) with the latest stable version of AutoIt and it behaves differently. Subtle differences are significant here because the function Fraction() should interpret 333333333333333 / 999999999999999 to be exactly equal to 1 / 3... and not equal to 333333333333333 / 1000000000000000. If accuracy fails, then the values may very quickly go out of range - or rather we end up back where we started.

Edited by czardas
Link to comment
Share on other sites

I'm sure you all wanted to know that 127215011248504 / 40493795751381 is a very good approximation of Pi. <_<

My head was spinning trying to figure this one out. The fraction was generated using a new function FractionApproximate() - now included in the first post along with two examples. The function allows you to limit the size of a fractions denominator: approximating the fraction as closely as possible to the original value within the imposed limitation. This is similar to rounding down a float, only sometimes more accurate.

Due to the tendancy for certain types of internal calculation to go out of range with the functions in this library, you have to monitor the upper bounds of the input. Adding or multiplying fractions with large numerators and denominators will generally return an error. These functions were designed to be used with simple fractions. There are frequently going to be cases where extreme accuracy is less critical. So if you want to combine floats with using fractions, and avoid out of range errors; instead of rounding you can use fraction approximation.

continued-fractions9.png

It appears that the method of 'Continued Fractions' is rarely seen nowadays, but it's very interesting nontheless. Here are some links which might make it easier to understand:

http://www.millersville.edu/~bikenaga/number-theory/continued-fractions/continued-fractions.html

http://www.millersville.edu/~bikenaga/number-theory/approximation-by-rationals/approximation-by-rationals.html

http://www.math.uiuc.edu/~hildebr/453.spring11/pi-cf.pdf


I should also mention that these function names will be prefixed with the customary underscore in due course, to comply with standard UDF practices.

Edited by czardas
Link to comment
Share on other sites

I don't know who's still at school or university here, but if you are chances are you are familiar with the current casio calculators, which give you answers in terms of fractions, square roots, and pi when it is reasonable to do so. For example, sin(pi/3) = sqrt(3)/2. With those limits, you could define a new kind of "fraction" that had 4 components: A/B * sqrt© * pi^D, Of course in that vein you can keep adding variables and layers of complexity ad nauseam.

Link to comment
Share on other sites

These casio calculators sound quite good. :)

Actually I wasn't planning on incorporating any trigonometry, and pi was used here as a test case for the approximation method above. Irrational roots are something that I would like to incorporate, but I haven't thought very deeply about it.

Edited by czardas
Link to comment
Share on other sites

  • 2 months later...

I have removed input size limitations for _Fraction(). Input size is now unlimited within the confines of AutoIt. The return values still remain within double precision (or maybe I should say quadruple precision since a fraction is made up of two doubles). With several functions, the extended flag is set to 1 when: either rounding or an approximation has occurred, or if one of the input parameters to _Fraction() is a float. The output is limited to regions detailed below.

;

Input Size Limits for _Fraction()
Unlimited within the confines of AutoIt (approximately) between -1e+308 and +1e+308
Smallest value (approximately) 1e-323

Negative Output Size Limits for _Fraction()
1e+015 /-1 Out of range
999999999999999 /-1 To -1/ 999999999999999 negative default range
-1/ 999999999999999 To -1/ 1999999999999998 rounded down to -1/ 999999999999999
-1/ 1999999999999998 To 0/-1 rounded up to 0/-1

Positive Output Size Limits for _Fraction()
0/1 To 1/ 1999999999999998 rounded down to 0/1
1/ 1999999999999998 To 1/ 999999999999999 rounded up to 1/ 999999999999999
1/ 999999999999999 To 999999999999999 /1 positive default range
1e+015 /1 Out of range

;

See first post. Documentation still needs updating. I also replaced the troublesome function __Expand() with __RawFraction(); it's a bit of a misnomer because the returned data is actually half-cooked. Some more changes will be added soon, but functionality will not likely be affected. What remains to be done are mainly optimization procedures and a bit more tidying. ;)

Edit

Forum code syntax highlighting still has issues. >_<

Edited by czardas
Link to comment
Share on other sites

Accuracy of Double Precision Compared with that of a Fraction

While there are still some considerations and small modifications to be made, it's time to start illustrating the use of this library with some easy examples. There are quite a few tests need doing. Here's the first - testing the precision of _FractionApproximate(). It turns out that 16 different approximations for Pi are viewed as exactly equal when converted back to a double. Of course they cannot be equal, but double precision is not accurate enough to differentiate between them. I consider that an excellent result. :D

;

#include 'Fraction.au3'

Global Const $fPi = 3.14159265358979

Local $aPi = _Fraction($fPi)
Local $aFr = $aPi, $iMaxDivisor

Do
    ConsoleWrite($aFr[0] / $aFr[1] & " = " & $aFr[0] & "/" & $aFr[1] & @LF)
    $iMaxDivisor = $aFr[1] -1
    $aFr = _FractionApproximate($aPi, $iMaxDivisor) ; Approximate Pi
Until @error

;

Output:

3.14159265358979 = 314159265358979/100000000000000
3.14159265358979 = 127215011248504/40493795751381
3.14159265358979 = 59729242861971/19012408497238
3.14159265358979 = 7756525524562/2468978756905
3.14159265358979 = 5433564190037/1729557198903
3.14159265358979 = 2322961334525/739421558002
3.14159265358979 = 787641520987/250714082899
3.14159265358979 = 747678292551/237993392204
3.14159265358979 = 39963228436/12720690695
3.14159265358979 = 28340180703/9020959694
3.14159265358979 = 11623047733/3699731001
3.14159265358979 = 5094085237/1621497692
3.14159265358979 = 1434877259/456735617
3.14159265358979 = 789453460/251290841
3.14159265358979 = 645423799/205444776
3.14159265358979 = 144029661/45846065
3.14159265358979 = 69305155/22060516
3.14159265358982 = 5419351/1725033
3.14159265358939 = 4272943/1360120
3.1415926535914 = 1146408/364913
3.14159265358108 = 833719/265381
3.14159265361894 = 312689/99532
3.14159265346744 = 208341/66317
3.14159265392142 = 104348/33215
3.1415926530119 = 103993/33102
3.14159292035398 = 355/113
3.14150943396226 = 333/106
3.14285714285714 = 22/7
3 = 3/1

;

09/02/2015 : A bug was discovered in _FractionApproximate(), fixed in the first post.

10/02/2015 : _FractionMod() now also allows approximations.

Edited by czardas
Link to comment
Share on other sites

When Not to Use Fractions

Using _Fraction() produces accurate results when the numbers involved are easy to factorize, and inaccuracies tend to multiply after a number of approximations.

On 29 iterations, the following example exposes the weakness of double precision, but if you change the number of iterations to 30, _Fraction() does not do quite so well. The reason for this is partially stated above. There is also the fact that double precision is not limited to exactly 15 decimal digits and I don't exactly know how numbers are stored internally by AutoIt. Numbers are rounded  to 15 digits by the interpreter before returning a result, and fraction cannot be any more accurate than the numbers provided. This reasoning is given greater credence by the results in the previous test. It also becomes apparent that the test below is not entirely a fair one.

;

#include 'Fraction.au3'

Global $g_iAPPROXIMATIONS = 0

Local $iVal = 1/3, $aFr = _Fraction(1, 3), $iIterations = 29 ; Change this value to 30

; Do
For $i = 1 to $iIterations
    $iVal *= 2/3
    $iVal += 1/3

    $aFr = _FractionMultiply($aFr, _Fraction(2, 3))
    If @extended Then $g_iAPPROXIMATIONS += 1

    $aFr = _FractionAdd($aFr, _Fraction(1, 3))
    If @extended Then $g_iAPPROXIMATIONS += 1
Next

; Undo
For $i = 1 to $iIterations
    $iVal -= 1/3
    $iVal /= 2/3

    $aFr = _FractionSubtract($aFr, _Fraction(1, 3))
    If @extended Then $g_iAPPROXIMATIONS += 1

    $aFr = _FractionDivide($aFr, _Fraction(2, 3))
    If @extended Then $g_iAPPROXIMATIONS += 1
Next

ConsoleWrite($iVal & @LF _
        & $aFr[0] / $aFr[1] &@LF _
        & $g_iAPPROXIMATIONS & " Approximations" & @LF)

;

Earlier I mentioned closed systems. A typical closed system might be (a selected set of) rhythmic values used in music, where every duration is expressed as being proportional to another. The numbers are generally quite small, and no matter how many notes you add together the result will probably remain within range. Using floats to model such a simple system is not particularly useful because note duration is always expressed as being proportional to a power of two: not to powers of ten. There is a certain degree of incompatibility.

So there is both an up side and a down side to using this library. Whle the continued fraction approximation method is extremely accurate, it only exists in the library to enable wider compatibility with various numeric datatypes. It is essential to check the extended return value in situations where an exact result is needed. This may seem a bit of a pain, but having the option offers new advantage - otherwise unavailable. These functions may only offer any real advantage in specific cases like the one I just mentioned: to simplify certain tasks.

Edited by czardas
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...