Recent

Author Topic: Fractions  (Read 40673 times)

typo

  • Hero Member
  • *****
  • Posts: 3051
Re: Fractions
« Reply #60 on: March 25, 2015, 07:05:08 pm »
Code: [Select]
var
  Str :string;

It has the value of Pi from Windows standard scientific calculator.
« Last Edit: March 25, 2015, 07:08:23 pm by typo »

typo

  • Hero Member
  • *****
  • Posts: 3051
Re: Fractions
« Reply #61 on: March 25, 2015, 07:29:13 pm »
Code: [Select]
  F := circular.FloatToFraction(StrToFloat(Str), 10, 10);
  WriteLn(IntToStr(F.Numerator) + '/' + IntToStr(F.Denominator));   // results 3/1
  F2 := wp.FloatToFraction(StrToFloat(Str), 0.00001);
  WriteLn(IntToStr(F2.Numerator) + '/' + IntToStr(F2.Denominator)); // results 355/113
 

garlar27

  • Hero Member
  • *****
  • Posts: 652
Re: Fractions
« Reply #62 on: March 25, 2015, 07:30:27 pm »
Maybe I'm saying something that someone already said, but I can't help tell you my experinece with fractions.

15 years ago (or more) I needed a simple program to build fractions from floating point values (I didn't wanted to do the excersices in home and wait until my next class to see if I did any mistake). Once I did the app, (with really few real test cases) I wanted to go further (addition, substraction, multiply, divide and simplify), and so I did.

I was very happy with the result but when I started to use it more and more, I started to note that in some cases the result was wrong due to rounding errors, or for not having a binary representation or for being unable to detect periodicity in float numbers.
This is something you will see more often when you have a long operations (let's say four or more fractions).

By the time I didn't know many things that I do now, and new activities took me out of my project. But I never forgot the problems I had, and whenever I read in the forum things that could help to solve the problem, I cant stop reading.

I think the most important thing is to define the type of number to use to avoid those rounding errors.

typo

  • Hero Member
  • *****
  • Posts: 3051
Re: Fractions
« Reply #63 on: March 25, 2015, 07:33:46 pm »
Code: [Select]
  F := circular.FloatToFraction(StrToFloat(Str), 10, 10);
  WriteLn(IntToStr(F.Numerator) + '/' + IntToStr(F.Denominator));   // results 3/1
  F2 := wp.FloatToFraction(StrToFloat(Str), 0.00000000000000001);
  WriteLn(IntToStr(F2.Numerator) + '/' + IntToStr(F2.Denominator)); // results 104348/33215
« Last Edit: March 25, 2015, 07:35:34 pm by typo »

typo

  • Hero Member
  • *****
  • Posts: 3051
Re: Fractions
« Reply #64 on: March 25, 2015, 07:40:40 pm »
Code: [Select]
  Str := '3.333333333333333333333333333333';
  F := circular.FloatToFraction(StrToFloat(Str), 10, 10);
  WriteLn(IntToStr(F.Numerator) + '/' + IntToStr(F.Denominator));   // results 10/3
  F2 := wp.FloatToFraction(StrToFloat(Str), 0.00000000000000001);
  WriteLn(IntToStr(F2.Numerator) + '/' + IntToStr(F2.Denominator)); // results 17/5

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: Fractions
« Reply #65 on: March 25, 2015, 07:47:37 pm »
Code: [Select]
  Str := '3.333333333333333333333333333333';
  F := circular.FloatToFraction(StrToFloat(Str), 10, 10);
  WriteLn(IntToStr(F.Numerator) + '/' + IntToStr(F.Denominator));   // results 10/3
  F2 := wp.FloatToFraction(StrToFloat(Str), 0.00000000000000001);
  WriteLn(IntToStr(F2.Numerator) + '/' + IntToStr(F2.Denominator)); // results 17/5

Bart's code: 10/3

Bart

circular

  • Hero Member
  • *****
  • Posts: 4196
    • Personal webpage
Re: Fractions
« Reply #66 on: March 26, 2015, 01:52:34 pm »
@typo: the comparisons you are making are not with the same precision.

Quote
Personally I find specifying the precision (how many digits after the decimalseparator must match) more intuitive.
I respect that.

Personally I find integers more attractive.

Quote
The "Stern-Brocot-Tree" could be in the fractions unit if "circular" is OK with this.
Sounds good to me.

Note that both function can coexist. We can overload the function. Depending on the situation, we may need one or the other.
« Last Edit: March 26, 2015, 02:00:33 pm by circular »
Conscience is the debugger of the mind

typo

  • Hero Member
  • *****
  • Posts: 3051
Re: Fractions
« Reply #67 on: March 26, 2015, 02:04:38 pm »

typo

  • Hero Member
  • *****
  • Posts: 3051
Re: Fractions
« Reply #68 on: March 26, 2015, 02:48:22 pm »
Code: [Select]
  Str := '3.333333333333333333333333333333';
  F := circular.FloatToFraction(StrToFloat(Str), 10, 10);
  WriteLn(IntToStr(F.Numerator) + '/' + IntToStr(F.Denominator));   // results 10/3
  F2 := wp.FloatToFraction(StrToFloat(Str), 0.01);
  WriteLn(IntToStr(F2.Numerator) + '/' + IntToStr(F2.Denominator)); // results 10/3

wp

  • Hero Member
  • *****
  • Posts: 11858
Re: Fractions
« Reply #69 on: March 26, 2015, 02:57:15 pm »
I am lost somehow in this long thread, but why is my name assigned to one of the FloatToFraction functions? I probably had posted a similar function here, but I can't find it any more, probably because it has been removed (copyright of the primary source (mathformum)?)

@Bart: Please remove my name from the copyright note in your fractions unit. I did not contribute anything except for a few forum postings.

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: Fractions
« Reply #70 on: March 26, 2015, 06:42:38 pm »
@Bart: Please remove my name from the copyright note in your fractions unit. I did not contribute anything except for a few forum postings.

Done.
I think the current FloatToFraction code is posted here by "circular"?

Bart

typo

  • Hero Member
  • *****
  • Posts: 3051
Re: Fractions
« Reply #71 on: March 26, 2015, 09:21:21 pm »
No. Excel converts the number 123.456 to 15432/125 (for format "???/???") or 123 57/125.

I found this simple algorithm (just varying numerator and denominator until the original number is best approximated) in http://stackoverflow.com/questions/95727/how-to-convert-floats-to-human-readable-fractions

Code: [Select]
procedure FloatAsFraction(AValue: Double; out ANumerator, ADenominator: Integer);
const
  EPSILON = 1E-6;
var
  fraction: Double;
begin
  ANumerator := 1;
  ADenominator := 1;
  fraction := ANumerator / ADenominator;

  while Abs(fraction - AValue) > EPSILON do
  begin
    if fraction < AValue then
      inc(ANumerator)
    else begin
      inc(ADenominator);
      ANumerator := Round(AValue * ADenominator);
    end;
    fraction := ANumerator / ADenominator;
  end;
end;

I think a more efficient way to do it is by means of continued fractions - a good explanation is in http://mathforum.org/library/drmath/view/51886.html, a bit down the page to the posting of Dr Peterson. I'm still searching to find a suitable implementation.

typo

  • Hero Member
  • *****
  • Posts: 3051
Re: Fractions
« Reply #72 on: March 26, 2015, 10:05:37 pm »
Maybe this can help to test:

Code: [Select]
program FloatToFractionFunctionTest;

{$mode objfpc}{$H+}
{$modeswitch advancedrecords}

uses
  Classes, SysUtils, Fractions2;

var
  Str :string;
  F1, F2 :TFraction;
begin
  Randomize;
  F1.Numerator := Random(9999999999);
  F1.Denominator := Random(9999999999);
  Str := FloatToStr(F1.Numerator / F1.Denominator);
  WriteLn('Float to convert: ' + Str);
  F1.Normalize;
  WriteLn('The result must be: ' + IntToStr(F1.Numerator) + '/' + IntToStr(F1.Denominator));
  F2 := FloatToFraction(StrToFloat(Str), 100, 100);
  WriteLn('The result is: ' + IIntToStr(F2.Numerator) + '/' + IntToStr(F2.Denominator)); 
  readln;
end.
       
« Last Edit: March 26, 2015, 10:16:17 pm by typo »

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: Fractions
« Reply #73 on: March 27, 2015, 12:00:03 am »
I think this will fail almost always (with big numbers):

F = test input
F1 and F2 are the result of 2 different FloatToFraction implementations.
Prec = used precision
(The lower the precision, the lower the change the test succeeds)

Code: [Select]
F          = 80901531/115151512
F1         = 34073573/48498754
F2         = 23413979/33326379
F1.ToFloat = 0.702565946333384
F2.ToFloat = 0.702565946333384
Prec       = 0.000000000000001

Here's the code I used to test the two impementations with random input and per input 15 iterations for different precisions:

Code: [Select]
procedure FTF_Test(Func1, Func2: TFracFunc; Name: String);
var
  F1,F2: TFraction;
  D1, D2, Prec, Diff1, Diff2: Double;
  i, Count: Integer;
  T: TextFile;
  procedure OpenT;
  begin
    if FileExists(Name+'_Test.txt') then
      Append(T)
    else
      Rewrite(T);
  end;
begin
  AssignFile(T,Name+'_Test.txt');
  OpenT;
  writeln(T,'Testing: ',Name);
  CloseFile(T);
//  Randomize;
  Count := 0;
  repeat
    D1 := Random;
    Prec := 0.1;
    for i := 1 to 15 do
    begin
      write('.');
      try
        F1 := Func1(D1, Prec);
        Diff1 := Abs(F1.ToFloat - D1);
        F2 := Func2(D1, Prec);
        Diff2 := Abs(F2.ToFloat - D1);
        if (Diff1 > Prec) or (Diff2 > Prec) then
        begin
          Inc(Count);
          OpenT;
          writeln(T,'Fail: ');
          writeln(T,'D          = ',D1:24:24);
          writeln(T,'F1.ToFloat = ',F1.ToFloat:24:24);
          writeln(T,'F2.ToFloat = ',F2.ToFloat:24:24);
          writeln(T,'Prec       = ',Prec:24:24);
          writeln(T,'Diff1      = ',Diff1:24:24);
          writeln(T,'Magnitude  = ',Round(Diff1/Prec));
          writeln(T,'Diff2      = ',Diff2:24:24);
          writeln(T,'Magnitude  = ',Round(Diff2/Prec));
          writeln(T,'F1         = ',F1.ToString);
          writeln(T,'F2         = ',F2.ToString);
          CloseFile(T);
          writeln;
          writeln('Fail: ');
          writeln('Fail: ');
          writeln('D          = ',D1:24:24);
          writeln('F1.ToFloat = ',F1.ToFloat:24:24);
          writeln('F2.ToFloat = ',F2.ToFloat:24:24);
          writeln('Prec       = ',Prec:24:24);
          writeln('Diff1      = ',Diff1:24:24);
          writeln('Magnitude  = ',Round(Diff2/Prec));
          writeln('Diff2      = ',Diff2:24:24);
          writeln('Magnitude  = ',Round(Diff2/Prec));
          writeln('F1         = ',F1.ToString);
          writeln('F2         = ',F2.ToString);
        end;
      except
        on E: Exception do
        begin
          Inc(Count);
          OpenT;
          writeln(T,'Exception: ',E.Classname,', Message: ',E.Message);
          writeln(T,'  D=',D1:16:16,' Prec=',Prec:16:16);
          CloseFile(T);
          writeln;
          writeln('Exception: ',E.Classname,', Message: ',E.Message);
          writeln('  D=',D1:16:16,' Prec=',Prec:16:16);
        end;
      end;
      Prec := Prec/10;
    end;
  until Count >= 15;
  OpenT;
  writeln(T,'Stopped after ',Count,' failures.');
  CloseFile(T);
  writeln('Stopped after ',Count,' failures.');
end;

It shows failure in the code from "mathforum":
Code: [Select]
Fail:
D          =        0.548813502304256
F1.ToFloat =        0.548813502361793
F2.ToFloat =        0.548813502302539
Prec       =        0.000000000010000
Diff1      =        0.000000000057537
Magnitude  = 6
Diff2      =        0.000000000001717
Magnitude  = 0
F1         = 29395/53561
F2         = 172924/315087

Bart
« Last Edit: March 27, 2015, 12:03:45 am by Bart »

typo

  • Hero Member
  • *****
  • Posts: 3051
Re: Fractions
« Reply #74 on: March 27, 2015, 01:59:07 pm »
WP's algorithm seems to be enough for me:

Code: [Select]
const
  EPSILON = 1E-6;
var
  Fraction: Double;
  ANumerator, ADenominator :integer;
  AValue : double;
  v1, v2 :integer;
begin
  ANumerator := (MAXINT);
  ADenominator := (MAXINT);
  v1 := Random(MAXINT);
  v2 := Random(MAXINT);
  AValue := v1 / v2;
  Fraction := ANumerator / ADenominator;
  while Abs(Fraction - AValue) > EPSILON do
  begin
    if Fraction < AValue then
    begin
      Dec(ADenominator);
      ANumerator := Round(AValue * ADenominator);
    end
    else
    begin
      Dec(ANumerator);     
    end;
    Fraction := ANumerator / ADenominator;
  end;
  ShowMessage(
              'entered value: ' + IntToStr(v1) + '/' + IntToStr(v2) + lineending +
              'found: ' + IntToStr(anumerator) + '/' + IntToStr(adenominator) + lineending +
              'difference:  ' + floattostr(avalue - (anumerator/adenominator))
              );
end;     
« Last Edit: March 27, 2015, 02:46:05 pm by typo »

 

TinyPortal © 2005-2018