fractions.Fraction limit numerator

fraction.Fraction.limit_denominator exists. But there is no obvious way to limit the numerator.

What is the best way to also limit the numerator?

(Goal: I need to limit the numerator also to 2**32, because TIFF files store fractions as two 32-bit integers.)

A crude approach:

from fractions import Fraction
def limit_32bit_rational(f: float) -> Fraction:
    ndigits = 15
    while True:
            r = Fraction.from_float(f).limit_denominator(1000000)
            if r.numerator < 2**32:
                return r
            f = round(f, ndigits)
            ndigits -= 1

Is there a better way?

Howdy Peter,

maybe a recursive interval bisection approach?

from fractions import Fraction
from math      import pi

limitI = (2**32 - 1)
def limit_numerator(valueF, numeratorLimitI=limitI, denominatorIntervalT=(limitI, 1)):
    
    #print (denominatorIntervalT)
    
    #get midst of denominator interval
    currDenominatorI = sum(denominatorIntervalT) // 2
    currFraction     = Fraction(valueF).limit_denominator(currDenominatorI)
    
    #recursive denominator interval bisection
    if    (currFraction == None) or (currFraction.numerator == numeratorLimitI):
          return currFraction

    elif  currFraction.numerator <  numeratorLimitI:
          if    (denominatorIntervalT[0], currDenominatorI) == denominatorIntervalT:
                return currFraction
          else:
                newDenominatorIntervalT = (denominatorIntervalT[0], currDenominatorI)
    else:
          if    (currDenominatorI, denominatorIntervalT[1]) == denominatorIntervalT:
                return None
          else:
                newDenominatorIntervalT = (currDenominatorI, denominatorIntervalT[1])
               
    #return result - None, if none found
    return limit_numerator(valueF, denominatorIntervalT=newDenominatorIntervalT)


print(pi)
print( float( limit_numerator(pi)     ) )
print(limitI + 0.12345)
print( float( limit_numerator(limitI + 0.12345) ) )

I wrote this in a hurry (and just tested it loosely). If you want to use it, please verify for yourself, that the function works properly for ALL cases needed…

Cheers, Dominik

PS: the function, as is, e.g. just works for positive values; but it should be easy to adapt it to work with negative ones too, if you need them too :slight_smile:

1 Like

Hi Peter,

It is too early in the day for me to prove that this code is correct,
or that it won’t get stuck in a loop, but I think this should do the
trick:

def limit_fraction(frac, limit):
    prev = None
    while frac != prev:
        print(frac)
        prev = frac
        a = (1/frac).limit_denominator(limit)
        frac = (1/a).limit_denominator(limit)
    assert abs(frac.numerator) <= limit
    assert abs(frac.denominator) <= limit
    return frac

The trick is to limit the numerator by limiting the denominator of the
reciprical, then flip again to limit the new denominator. The print call
is just so that you can monitor the value changing.

A few examples:

>>> from fractions import Fraction
>>> limit_fraction(Fraction(0.1), 2**32)
3602879701896397/36028797018963968
1/10
Fraction(1, 10)


>>> limit_fraction(Fraction(7.467890032218), 2**32)
8408096691585207/1125899906842624
1275621206/170814139
Fraction(1275621206, 170814139)


>>> limit_fraction(Fraction(math.pi), 10000)
884279719003555/281474976710656
355/113
Fraction(355, 113)
2 Likes

Hi Steven,

nice idea to use the reciprocal!

Unfortunately, I am not able to prove anything now too - for me it is too late in the day now… :slight_smile:

Cheers, Dominik

Thanks all.

Another attempt:

def limit_fraction(frac, limit):
	return frac.limit_denominator(max(1, min(limit, int(limit/frac))))

It seems to give the same results as the iterative version posted above. (But I also have no proof.)

1 Like

Hi Peter,

so, now it is time for a little Monte Carlo test / comparison, right?

Until the week end I am too busy, but then, I should be able to find a little spare time for that…

Cheers, Dominik

1 Like

Interesting idea. I tried pip install pytest-quickcheck with this:

import pytest
from fractions import Fraction

def limit_fraction(frac, limit):
	return frac.limit_denominator(max(1, min(limit, int(limit/frac))))

@pytest.mark.randomize(limit=int, min_num=1, ncalls=1000)
def test_limit_fraction(f: float, limit):
    result = limit_fraction(Fraction(f), limit)
    assert result.numerator < limit
    assert result.denominator < limit
    assert abs(f - result) < 1/result.denominator
    assert f == result or result.numerator * 2 > limit or result.denominator * 2 > limit

And py.test limit_test.py claimed 1’000’000 randomized test runs all passed.

Howdy Peter,

good start and interesting test module!

We furthermore already have 4 competitors (different functions / approaches) - so we also can compare there performances on the interval -(2^31 - 1) … (2^31 - 1) directly, right?

What is the best performance?

  1. best precision
  2. fastest computation

Right? Did I forget anything?

Cheers, Dominik

For that, I already have extended the recursive bisection approach function - it now also accepts negative floats:

from fractions import Fraction
from math      import pi
from math      import copysign

limitI = (2**31 - 1)
def limit_numerator(valueF, numeratorLimitI=limitI, denominatorIntervalT=(limitI, 1)):
    
    #print (denominatorIntervalT)
    
    #allow negative valueF-s
    absValueF = abs(valueF)
    sgnValueI = int(copysign(1, valueF))
    
    #get midst of denominator interval
    currDenominatorI = sum(denominatorIntervalT) // 2
    currFraction     = Fraction(absValueF).limit_denominator(currDenominatorI)
    
    #recursive denominator interval bisection
    if    (currFraction == None) or (currFraction.numerator == numeratorLimitI):
          return (sgnValueI * currFraction)

    elif  currFraction.numerator <  numeratorLimitI:
          if    (denominatorIntervalT[0], currDenominatorI) == denominatorIntervalT:
                return (sgnValueI * currFraction)
          else:
                newDenominatorIntervalT = (denominatorIntervalT[0], currDenominatorI)
    else:
          if    (currDenominatorI, denominatorIntervalT[1]) == denominatorIntervalT:
                return None
          else:
                newDenominatorIntervalT = (currDenominatorI, denominatorIntervalT[1])
               
    #return result - None, if none found
    return limit_numerator(valueF, denominatorIntervalT=newDenominatorIntervalT)


#crude test of the function
testFloats = [-limitI-1.0, -limitI-0.123, -pi, -0.123, 0.0, 0.123, pi, limitI+0.123, limitI+1.0 ]
for testF in testFloats:
    print (testF)
    fraction = limit_numerator(testF)
    if    fraction == None:
          print ("------------")
    else:
          print (float(fraction))
          print (fraction)
    print ()

PS: preview…:

from random import random
from time   import time

limitF             = float(2**31 - 1)
meanRelErrorF      = 0.0
meanExecTimeF      = 0.0
numberOfTestsI     = 10000

for looper in range(numberOfTestsI):
    randF          = 2.0 * random() * limitF - limitF
    startF         = time()
    fraction       = limit_numerator(randF)
    endF           = time()
    currRelErrorF  = abs(float(fraction) - randF) / abs(randF)
    meanRelErrorF += currRelErrorF
    meanExecTimeF += (endF - startF)
    
print ("Mean relative error:", (meanRelErrorF / float(numberOfTestsI)))
print ("Mean execution time:", (meanExecTimeF / float(numberOfTestsI)))
  • using the recursive bisection function - leads to:

Mean relative error: 1.2913023476519324e-10
Mean execution time: 0.0006371458530426026

Cheers, Dominik

PS: the tests should be done for all 4 competitors on the very same test numbers, if you ask me…

Howdy Peter, Howdy Steven,

sorry for the delay - today I’ve done said little comparison. The test might not meet the highest scientific standards - but it’s results nevertheless might give a good first impression of the performances of the different proposed algorithm versions, this is the belonging code:

from fractions    import Fraction
from math         import pi
from math         import copysign

from numpy.random import uniform
from time         import time

from os           import linesep


#limit
limitI = (2**31 - 1)


### limit_32bit_rational ###
def limit_32bit_rational(f):
    ndigits = 15
    while True:
            r = Fraction.from_float(f).limit_denominator(1000000)
            if r.numerator < limitI:
                return r
            f = round(f, ndigits)
            ndigits -= 1

            
### limit_numerator ###
def limit_numerator(valueF, numeratorLimitI=limitI, denominatorIntervalT=(limitI, 1)):
    
    #allow negative valueF-s
    absValueF = abs(valueF)
    sgnValueI = int(copysign(1, valueF))
    
    #get midst of denominator interval
    currDenominatorI = sum(denominatorIntervalT) // 2
    currFraction     = Fraction(absValueF).limit_denominator(currDenominatorI)
    
    #recursive denominator interval bisection
    if    (currFraction == None) or (currFraction.numerator == numeratorLimitI):
          return (sgnValueI * currFraction)

    elif  currFraction.numerator <  numeratorLimitI:
          if    (denominatorIntervalT[0], currDenominatorI) == denominatorIntervalT:
                return (sgnValueI * currFraction)
          else:
                newDenominatorIntervalT = (denominatorIntervalT[0], currDenominatorI)
    else:
          if    (currDenominatorI, denominatorIntervalT[1]) == denominatorIntervalT:
                return None
          else:
                newDenominatorIntervalT = (currDenominatorI, denominatorIntervalT[1])
               
    #return result - None, if none found
    return limit_numerator(valueF, denominatorIntervalT=newDenominatorIntervalT)


### limit_fraction ###
def limit_fraction(fraction, limit=limitI):
    frac = Fraction(fraction)     #line inserted, as the other functions accept floats (not Fraction-s)
    prev = None
    while frac != prev:
        prev = frac
        a = (1/frac).limit_denominator(limit)
        frac = (1/a).limit_denominator(limit)
    assert abs(frac.numerator) <= limit
    assert abs(frac.denominator) <= limit
    return frac


### limit_fraction_II ###
def limit_fraction_II(frac, limit=limitI):
    #'Fraction' inserted, as the other functions accept floats (not Fraction-s)
    return Fraction(frac).limit_denominator(max(1, min(limit, int(limit/frac))))


### test ###
class Test(object):
      """ Contains the cumulated result of all the tests done on the 'limitNumeratorFct' 
          using the 'singleTestRun' method multiple times.                               """
        
      def __init__(self, limitNumeratorFctS):
          """ Initialisation. """
           
          self.testFctNameS      = limitNumeratorFctS
          self.testFct           = eval(limitNumeratorFctS)
          self.maxRelErrorF      = 0.0
          self.cumRelErrorF      = 0.0
          self.cumExecTimeF      = 0.0
          self.numberOfTestsI    = 0
        
        
      def __str__(self):
          """ Returns the string representation of the (total) test results. """
            
          resultS  = "### Results of the Test of %s ###%s" % (self.testFctNameS, linesep)
          resultS += "Number of tests: %d%s"               % (self.numberOfTestsI, linesep)
          resultS += "Max  relative error: %e%s"           % (self.maxRelErrorF, linesep)
          resultS += "Mean relative error: %e%s"           % (self.cumRelErrorF / float(self.numberOfTestsI), linesep)      
          resultS += "Mean execution time: %e [s]%s"       % (self.cumExecTimeF / float(self.numberOfTestsI), linesep)
            
          return resultS
        
        
      def singleTestRun(self, randomValueF):
          """ Adds the results belonging to the test run using randomValueF as the test value
              to the cumulated ones.                                                          """
            
          startF                 = time()
          fraction               = self.testFct(randomValueF)
          endF                   = time()
        
          #add current relative error to cumulated one
          currRelErrorF          = abs(float(fraction) - randomValueF) / abs(randomValueF)
          self.cumRelErrorF     += currRelErrorF
        
          #determine the maximal relative error
          if currRelErrorF > self.maxRelErrorF:
             self.maxRelErrorF = currRelErrorF
    
          #add the current excution duration to cumulated one
          self.cumExecTimeF += (endF - startF)
            
          #increment number of test runs
          self.numberOfTestsI += 1
          
        
#uniform distribution of random values in the range [-2^31..(2^31-1)[            
monteCarloValuesA  = uniform( -float(limitI+1), float(limitI), 500000 )

#container dict for test results
testResults = { "limit_numerator"      : Test("limit_numerator"),      \
                "limit_32bit_rational" : Test("limit_32bit_rational"), \
                "limit_fraction"       : Test("limit_fraction"),       \
                "limit_fraction_II"    : Test("limit_fraction_II")     }

#main / test loop
testFctT = ("limit_numerator", "limit_32bit_rational", "limit_fraction", "limit_fraction_II")
for randomF in monteCarloValuesA:
    for testFctS in testFctT:
        testResults[testFctS].singleTestRun(randomF)

#display results
for testFctS in testFctT:
    print (testResults[testFctS])

And this is the belonging output:

result

Interesting, right?

Cheers, Dominik

PS: it looks like “limit_numerator” and “limit_fraction” could be mathematically equivalent?

Hi Dominik,

You said:

“”"
And this is the belonging output:

result

Interesting, right?
“”"

Sadly, not. All I see is a cryptic and unreachable “upload” URL.

As far as your code, I would expect that your timing code is measuring
almost nothing but noise. For measuring small, fast snippets of code,
you should use the timeit module.

I’m not sure what you hope to demonstrate by computing the cumulative
errors. What you are actually calculating is not errors but the
differences between the fraction before and after limiting the numerator
and denominator.

An example: let’s take the exact fraction value of math.pi:

x = Fraction(math.pi)
assert x == Fraction(884279719003555, 281474976710656)

Now let me limit the denominator of that using two methods:

# Method 1
y = x.limit_denominator(10)  # 22/7
float(y - x)
# --> 0.0012644892673497412

But that’s the correct result for what you asked. 22/7 is the closest
possible fraction with the denominator below 10. So the error term
should be 0.

Here is my second method:

z = x + 0 
float(z - x)
# --> 0.0

But the second method is a totally useless, buggy method that doesn’t
limit the denominator at all. But our “error calculation” says that it
has no error. Oops.

One final thing: you gather the functions to be tested by passing the
names of the functions as strings, then calling eval to evaluate the
string and return the function. That is unnecessary work.

# Don't do this:
>>> print(eval('len'))
<built-in function len>

# When you can do this:
>>> print(len)
<built-in function len>

Instead of passing the list of function names

testFctT = ("limit_numerator", "limit_32bit_rational", "limit_fraction", "limit_fraction_II")

just pass the functions themselves:

testFctT = (limit_numerator, limit_32bit_rational, limit_fraction, limit_fraction_II)

and remove the unnecessary call to eval.

Hi Steven,

that is unfortunate - you should see a screenshot image of the results - as I do; I do not know what the problem with this is, sorry… But I think, it should not be a big effort to copy the code and run it on your machine - to get said output for yourself, right?

It seems that your expectation is wrong.

The cumulative error is divided by the number of test runs at the end, please have a look at the __ str __ method.

I am calculating the differences between the result of each limit*-function and the random FLOAT it has been fed with:

see “abs(float(fraction) - randomValueF) / abs(randomValueF)”

As the task, as I understood it and your comment suggest it too, is to find the fraction closest to said original float, determining said differences is -statistically- a good description of the task - if you ask me:

Please note that my little test is not designed to determine exact (absolute) errors or runtimes (and in particular not of single measurements) but just to COMPARE the (mean resp. overall) performance of the four algorithm versions (so, your “noise” should cancel out sufficiently, right?). It is a statistical approach. If you have a look on my code from this POV, this should clear up your objections (by the way, this also is why I did not use timeit - as I do not compare single measurements).

You might have overlooked the usage of “self.testFctNameS” - I use it for printing out the result with a nice headline. So, no…

Cheers, Dominik

Hi Dominik,

What is wrong is that the Discuss software does not email images, it

emails an internal markdown code that is unviewable.

But why are you taking screenshots of text? Screenshots of GUI

applications makes sense: if you want to show a problem with a GUI, you

need to see the graphical elements. But your results are text.

Not everyone can see screenshots at all. I know that there is at least

one highly respected core Python developer whose eyesight has

deteriated to the point that he is (I think) legally blind. I’ve worked

with no fewer than three developers who are likewise are legally blind,

all had extreme problems dealing with screenshots. I know at least one

person who is completely blind and uses a screen reader to read emails.

I never realised that he was blind until he apologised in advance for

not being able to understand something I had written because his screen

reader was mispronouncing the words and he couldn’t tell what they were.

Screen shots of text discriminate against the visually impaired and

blind. They are also inconvenient and annoying for many fully sighted

readers too.

I said:

"I would expect that your timing code is measuring almost nothing but

noise."

and you disagreed:

“It seems that your expectation is wrong.”

What makes you say that?

I asked what you were hoping to demonstrate with the cumulative errors,

and you responded by saying:

"The cumulative error is divided by the number of test runs at the

end, please have a look at the __ str __ method."

Yes, I know that. But I still don’t know why you are calculating those

errors in the first place. What do you think the errors show?

Are you trying to find the algorithm with the smallest error? The

smallest error is the identity function that just returns the number

unchanged. Walk me through your logic as if I were five please.

You said:

“”"

I am calculating the differences between the result of each

limit*-function and the random FLOAT it has been fed with:

see “abs(float(fraction) - randomValueF) / abs(randomValueF)”

“”"

Yes, I know that. Every float is equal to an exact fraction.

(To be pedantic: only the finite floats. NANs and INFs excepted.)

For example, the float math.pi is exactly equal to the fraction

884279719003555/281474976710656.

If we reduce that fraction to have a smaller denominator, we are

naturally going to introduce some difference. The fraction 22/7 is the

closest fraction to math.pi with the denominator less than 10.

The difference between math.pi and 22/7 is 0.0012644892673497412.

(I know that you are calculating the relative error, not the absolute

error. You are dividing by the original number. But that doesn’t change

my point, so for simplicity I am going to continue with absolute error.)

The difference between math.pi and 311/99 is even smaller, just

0.00017851217565170184, so that’s better, right?

Not if we want to limit the denominator to be less than ten! 99 is not

less than ten.

In your case, you have an additional constraint: you also want to limit

the numerator, not just the denominator. But the principle applies: we

are not just trying to find the smallest difference between the original

number and the new number. For that, we could just use the original

number unchanged.

So the bottom line here, if we have four different algorithms for

limiting the numerator and denominator of a fraction, they must

return the same (numerator, denominator) pair. If they don’t, some of

them are simply wrong and returning the wrong result.

To be clear:

If any two algorithms return a different (num, den) pair, then

at least one of them is wrong. They might both be wrong, but they

can’t both be right. Only one num/den fraction can be the closest to the

original number.

If all four return the same pair, that’s reasonable evidence that they

are probably correct. It is unlikely that four independent algorithms

would all just happen to return the same wrong answer. (Very unlikely,

but not impossible.) If any one of them is different, that’s a good sign

that it is the wrong answer.

But if all four are different, that shows that at least three of them

are wrong, maybe all four are wrong. It’s not a matter of pulling out

the one which is least wrong on average and calling it the best.

Looking at the error terms and picking the function with the smallest

error terms is the wrong way to analyse this. You are measuring the

wrong thing.

You suggested that you are trying to:

"COMPARE the (mean) performance of the four algorithm versions (so, your

“noise” should cancel out sufficiently, right?)."

I’m afraid not. Errors only cancels out when they are equally likely to

be positive or negative. If I have a piece of wood exactly 78.3 cm long,

and ask six people to measure it, they are likely to get results

something like this:

77.9, 78.0, 78.2, 78.5, 78.5, 78.7

and the errors cancel out. (In this case, they cancel out exactly,

because I made the numbers up. In the real world, we are rarely that

lucky.)

But noise when timing code is not like that. The errors are always

one-sided: your measured time will never have a negative error.

Suppose the “true” time it takes your CPU to compute a result is, let’s

say, exactly 10µs. Then your timing code will probably

measure something like:

12, 15, 16, 18, 19, 26 µs 

and the best estimate of the true time to run the code is the minimum,

12µs, not the mean, 17.7µs.

Noise does not cancel out because it always adds time to the

measurement, it never subtracts it. Taking the average just averages the

noise. It gets you no closer to the actual execution cost of the code,

it just moves you further away.

Worse, if the code snippet is small and fast enough, the noise might

completely overwhelm the measurement. If your results are 12µs etc

above, we have no way of knowing that the true computational cost is

actually 10µs. It might be 1µs, and the rest of the measurement is all

noise.

This is why we have the timeit module. The timeit module is designed to

measure the running cost of small code snippets, with as little noise

as possible.

It cannot eliminate all noise – nothing can. But it can try to make it

as small as possible, within the Python interpreter at least. It can’t

do anything about noise from the OS, e.g. other processes running.

Regarding the use of eval on the function names, passed as strings, no,

I did not overlook the use of self.testFctNames to print the names of

the functions. Although you might have overlooked that functions know

their own names and you can print those :slight_smile:

>>> def func(): pass

... 

>>> func.__name__

'func'

Inside a Python script, there is little need to pass function names

separately from the function themselves. The only exception I can think

of is if you are getting the names from user-provided data, e.g. read

from a file, or a command line, or a GUI input widget (say, for a

calculator app). You can only get user input as strings.

Even there, especially there, you should not use eval to evaluate the

string to get the function. Using eval on untrusted user input is

very dangerous. Instead, use a global lookup:

func = globals()[name]

But in your case, you don’t need that since you can just pass the

function object and retrieve the name from the function, not the

function from the name.

1 Like

Hi Steven,

that is a lot of text you have written. I will need a little to read and answer it (not today)

  • but I am not sure that I want to do it that way.

In the end, all is quite easy - if you e.g. just want to know, which algorithm is the fastest, a constant time offset to ALL run time measurements does not matter as it does not change the order of the results.

If said time offset is not strictly constant, but e.g. normally distributed around an average value, the message stays the same, if you do enough measurements - as the fluctuation then “cancels out” sufficiently.

The idea of using the differences between the random numbers and the results of each algorithm version is quite similar.

There is a difference between calculating things exactly and just estimating things. The former is not necessary for every riddle you want to solve and the latter is quite common in e.g. physics, when the former is not necessary resp. comes with too much effort.

Belonging keywords are equation vs. inequation, I think.

When talking about my code, we are talking about the latter. If you want the former, you have to program it yourself.

Cheers, Dominik

Further to my previous comments about timing code, this blog post

contains some good information:

https://blog.kevmod.com/2016/06/benchmarking-minimum-vs-average/

So I thought I would do some more experiments. In particular, I wanted

to find out whether the measured times were symmetrical or skewed.

The following may be a little complicated to understand if you don’t

have a good background in statistics, If it’s too complicated, feel free

to ask questions, or just skip to the end where I run a second test.

I’ve timed how long it takes to run this small snippet of code:

(len(s)+1)*7

Firstly I used timeit:

>>> import timeit

>>> t = timeit.Timer("(len(s)+1)*7", setup="s='abcd'")

>>> a = t.repeat(repeat=1000) 

That gives me 1000 measurements. Here are some statistics from those

measurements:

>>> from statistics import mean, stdev, median

>>> mean(a)

0.07665841747028754

>>> median(a)

0.07488817302510142

>>> stdev(a)

0.008650796561434814

>>> min(a)

0.06562498677521944

>>> max(a)

0.1572880893945694

Obviously the times you will get on your computer will be very

different, depending on the speed of your CPU and amount of memory, and

whatever other programs you are running.

Notice that the maximum value is a lot further away from the mean and

median than the minimum: about 0.09 compared to 0.02. That’s more than

four times as distant, which is a lot of the data is symmetrical rather

than skewed. I wanted to find out just how skewed the data is.

Calculating the third moment skew is tricky, so instead I used Pearson’s

second coefficient of skewness:

>>> 3*(mean(a) - median(a))/stdev(a)

0.6139010781080614

This skewness measurement is a number between -3 and 3. If the

underlying data, the timing measurements, are symmetrically distributed,

then it should be close to zero. How close though?

To get that, we need the “critical values”. The critical values tell us

that, if the data is actually normally distributed, and so

symmetrical, 90% of the time we will get a skewness between the two

critical values. If we get a skewness outside of those two values, then

there is only a 5% chance that the data actually was normally

distributed.

Unfortunately there are no easily accessible published tables of

critical values for Pearson’s second skewness, so I wrote a script to

estimate them. (Source code for that is available on request.) I got

critical values of (-0.1179820200198676, 0.11780766394051344).

That tells us that if the underlying data was actually normally

distributed, and therefore symmetrical with an actual skewness of 0.0,

and we measured the skewness with 1000 samples, 90% of the time we would

get a measured skewness between -0.118 and 0.118.

The value that we actually got, 0.614, was way out of that range,

suggesting very strongly that our data was normally distributed, and so

probably not symmetrical. Our measured times are probably includes a few

small values, then dominated by a huge pile of moderate values, and then

a long, thin tail leading to much larger values.

(“Much larger” is relative of course.)

Something like a log-normal distribution, perhaps. (See the blog post I

linked to.)

And that suggests that using the minimum value, not the mean, is the

better statistic to use.

Thinking about what we are measuring, that makes sense. We are measuring

the time taken to run a code snippet. That time has a hard limit of how

quickly my CPU can run those instructions as fast as possible, with

absolutely nothing else going on in the system. You can’t get faster

than that. And it is unusual for there to be absolutely nothing else

running during that time. There’s always something else running, the OS,

another process, the instructions may not be in the CPU cache, etc. So

the measured time will always be a little bit greater than the hard

minimum.

But occasionally there’s a lot of other things happening, and the

measured time is a lot greater than the hard minimum.

So our measured values will have a hump somewhat greater than the

measured minimum, which is greater than the hard minimum by some unknown

amount, with a long tail past the hump.

Let’s do the measurement again without using timeit. Here is my timing

test function:

def test():

    from time import time

    s = 'abcd'

    elapsed_time = 0.0

    for i in range(1000000):  # timeit uses a default of 1000000 loops

        start = time()

        _ = (len(s)+1)*7

        elapsed_time += time() - start

    return elapsed_time

I call that test function a thousand times to get a thousand

measurements, each of one million loops, just as I did using timeit.

>>> b = [test() for i in range(1000)]

>>> min(b)

0.11760973930358887

>>> mean(b)

0.14290602612495423

>>> max(b)

0.2201399803161621

>>> stdev(b)

0.012805640207040298

The measured times here are almost twice as big as the times measured

using timeit, and the variability is greater too. How can that be? It is

not that timeit has some sort of “turbo” button that makes

(len(s)+1)*7 run faster than normal. And my computer hasn’t become

suddenly slower.

It can only be that the measurements made in the test function are

measuring more noise. About half the elapsed time is just noise that has

nothing to do with the code snippet we are trying to run.

The faster the code snippet, the larger that proportion which is noise

will be. The slower the code snippet, the smaller the proportion will be

noise.

1 Like

Hi Steven,

nice, interesting analysis!

But concerning my code / test, it should not matter, which kind of distribution is underlying (or how “skew” it is) - as long as it is the very same for the test branches of all tested algorithms - or in other terms: as long as the mean offsets do not differ too much.

From theory to practice: have a look at the outcome. You’ll see, that:

as, at least in my test run, they had the exact same “error” values - taking the relatively big number of single tests (500000) into account, it is unlikely, that this just is coincidence… Next step could be to verify that they indeed always have the same results.

the run time differences between the different algorithms are of order of magnitudes. So, I guess, our statistics already is good enough to choose the “winner”. But, it indeed would be a good idea, to verify that outcome using the minimal run times of each one too.

Cheers, Dominik

Hi Steven,

I did another test run to be able to make you happy by providing the results in text form too, here they are:

### Results of the Test of limit_numerator ###
Number of tests: 500000
Max  relative error: 4.635435e-10
Mean relative error: 1.288841e-10
Mean execution time: 2.192438e-03 [s]
Min  execution time: 9.450912e-04 [s]

### Results of the Test of limit_32bit_rational ###
Number of tests: 500000
Max  relative error: 1.615075e-09
Mean relative error: 1.084075e-10
Mean execution time: 5.961003e-04 [s]
Min  execution time: 1.692772e-05 [s]

### Results of the Test of limit_fraction ###
Number of tests: 500000
Max  relative error: 4.635435e-10
Mean relative error: 1.288841e-10
Mean execution time: 1.513034e-04 [s]
Min  execution time: 5.507469e-05 [s]

### Results of the Test of limit_fraction_II ###
Number of tests: 500000
Max  relative error: 3.067226e-04
Mean relative error: 1.384882e-09
Mean execution time: 7.896068e-05 [s]
Min  execution time: 2.288818e-05 [s]

I also added a line, checking whether the return values of “limit_numerator” always are the same as the return values of “limit_fraction” - and they were. :face_with_hand_over_mouth:

As you can see, I also added each minimal execution time, as proposed by you. It is a good “double-check” opportunity from my POV.

But please note, that I do not agree with your assumption, that the minimal execution time is the better statistics in our case.

Your assumption might be a good one, if you are talking about algorithms with a fixed execution time. In our case, the execution time depends on the number of iterations / recursions necessary for the algorithms to find each result. It obviously varies heavily with the random float given to the function as the parameter.

It is similar with your timeit approach. If you use timeit, you determine the execution time by thousands of test runs WITH THE SAME PARAMETER, means: with the same number of iterations / recursions. The belonging statement then is, ummm, let’s say, a little limited…

But let’s come back to the results given above - my interpretation of them would be alike:

  1. the relatively big “Max relative error” of “3.067226e-04” might be a hint, that the version “limit_fraction_II” sometimes performs poorly in mathematical terms.

  2. the fact, that the return values of “limit_numerator” and of “limit_fraction” have been the same in all single tests, is a good sign. Taking into account, that both algorithm use different -but both plausible (if you ask me)- approaches, this might be an indication, that they both work properly - not more, not less.

  3. As “limit_fraction” obviously is significantly faster than “limit_numerator”, this should be “the candidate” for further examinations. Which ones are necessary depends on the requirements - so, that is a question, which Peter has to clear up. Maybe even all algorithm versions already are good enough for his task…

The performance of “limit_32bit_rational” might seem at eye level in terms of the examined “deviation / error” and “execution time”, but it suffers from obviously not leading to the same results as “limit_numerator” and “limit_fraction” as well as from a slightly bigger, maximal relative error (although the latter does not necessarily mean anything, as you have explained in your previous posts).

Do you agree so far?
Cheers, Dominik

Hi Dominic,

Refresh my memory: is the intention here to limit both the numerator
and the denominator of the fraction, or just the denominator?

If just the denominator, fractions already support that.

If both, I think you may need to test your code a little better before
worrying about which is fastest:

>>> x = Fraction(limitI*100+1, 2)
>>> limit_32bit_rational(x)
Traceback (most recent call last):
  ...
TypeError: Fraction.from_float() only takes floats, not Fraction(214748364701, 2) (Fraction)

>>> limit_32bit_rational(float(x))
Fraction(0, 1)


>>> limit_numerator(x)
>>> 


>>> limit_fraction(x)
Traceback (most recent call last):
  ...
ZeroDivisionError: Fraction(1, 0)


>>> limit_fraction_II(x)
Fraction(107374182350, 1)

Every one of those functions is buggy.

Hi Steven,

This range contains the smallest and biggest number which sensibly can be represented under this conditions, right (the correct lower limit should be -(2^31), I know, the “-1” there just was a simplification then)?

So, it is not very sensible to state

while using an out of the range number as justification.

And it also does not make sense to feed a Fraction

into a function, expecting a float:

,right?

But as you also did not answer to the main statements in my last two posts, I guess this discussion has come to an end.

Cheers, Dominik