Python -- floating point arithmetic

[Wolfram Hinderer]

On 7 Jul., 19:32, Ethan Furman <et... at stoneleaf.us> wrote:
> Nobody wrote:
> > On Wed, 07 Jul 2010 15:08:07 +0200, Thomas Jollans wrote:
>
> >> you should never rely on a floating-point number to have exactly a
> >> certain value.
>
> > "Never" is an overstatement. There are situations where you can rely
> > upon a floating-point number having exactly a certain value.
>
> It's not much of an overstatement.  How many areas are there where you
> need the number
> 0.100000000000000005551115123125782702118158340454101562500000000000?
>
> If I'm looking for 0.1, I will *never* (except by accident ;) say
>
> if var == 0.1:
>
> it'll either be <= or >=.

The following is an implementation of a well-known algorithm.
Why would you want to replace the floating point comparisons? With
what?

(This is toy-code.)

#####
from random import random

def min_cost_path(cost_right, cost_up):
    """ return minimal cost and its path in a rectangle - going up and
right only """
    cost = dict()
    size_x, size_y = max(cost_right)

    #compute minimal cost
    cost[0, 0] = 0.0
    for x in range(size_x):
        cost[x + 1, 0] = cost[x, 0] + cost_right[x, 0]
    for y in range(size_y):
        cost[0, y + 1] = cost[0, y] + cost_up[0, y]
        for x in range(size_x):
            cost[x + 1, y + 1] = min(cost[x, y + 1] + cost_right[x, y
+ 1],
                                     cost[x + 1, y] + cost_up[x + 1,
y])

    #compute path (reversed)
    x = size_x
    y = size_y
    path = []
    while x != 0 and y != 0:
        if x == 0:
            y -= 1
            path.append("u")
        elif y == 0:
            x -= 1
            path.append("r")
        elif cost[x - 1, y] + cost_right[x - 1, y] == cost[x, y]: # fp
compare
            x -= 1
            path.append("r")
        elif cost[x, y - 1] + cost_up[x, y - 1] == cost[x, y]: # fp
compare
            y -= 1
            path.append("u")
        else:
            raise ValueError

    return cost[size_x, size_y], "".join(reversed(path))


if __name__ == "__main__":
    size = 100
    cost_right = dict(((x, y), random()) for x in range(size) for y in
range(size))
    cost_up = dict(((x, y), random()) for x in range(size) for y in
range(size))
    print min_cost_path(cost_right, cost_up)