[EMAIL PROTECTED] wrote:
>
> -jn- wrote:
>
> If speed is the objective (rather than total correctness ;-) ...
>...
> placing the "most likely" branch first. This rearrangement saves
> just over 25%, according to my quick-and-dirty benchmarking:
>
> >> x: now/time loop 10000 [y: fib 1.0 1.0 100] now/time - x
> == 0:01:37
> >> x: now/time loop 10000 [y: fib 1.02 1.0 100] now/time - x
> == 0:01:12
>
>...
>
> The speed-up seemed unbelievable to me (placing the most probable case of
> EITHER first shouldn't have any influence on speed in this case) and I made
> my own computations. The times were exactly the same with the same data here
>
SHORT VERSION:
The fault is with my hasty description, not with the timings. (I'm also
running 2.2.0.3.1, which was used for the actual timings above on a
90MHz Pentium.) Instead of "placing the ^"most likely^" branch first",
I should have said "rearranging the tests to minimize the number of
boolean expressions evaluated". Sorry for the sloppy language.
BORING DETAILS:
In the first recursive code posted, the function was equivalent to
fib: func [a1 a2 n] [
either n = 1 [
a1
][
either n = 2 [
a2
][
fib a2 a1 + a2 n - 1
]
]
]
where one normally expects 'n to be of interesting size (much greater
than 2 for the initial invocation). For this approach, the count of
boolean evaluations as a function of 'n is
n bexp
1 1 ; 1 = 1
2 2 ; 2 = 1, 2 = 2
3 4 ; 3 = 1, 3 = 2, 2 = 1, 2 = 3
4 6 ; 4 = 1, 4 = 2, 3 = 1, 3 = 2, 2 = 1, 2 = 2
... ...
n 2n - 2 ; for n>1
where all but the last recursive call (for interesting values of n)
of the above skeleton has to test all conditions before arriving at
the recursive branch.
My immediate thought was to rewrite the above as
fib1: func [a1 a2 n] [
either n > 2 [
fib1 a2 a1 + a2 n - 1
][
either n = 2 [
a2
][
a1
]
]
]
where the number of boolean evaluations is
n bexp
1 2 ; 1 > 2, 1 = 2
2 2 ; 2 > 2, 2 = 2
3 3 ; 3 > 2, 2 > 2, 2 = 2
4 4 ; 4 > 2, 3 > 2, 2 > 2, 2 = 2
... ...
n n ; for n>1
which means that the second version has to evaluate (approximately)
half as many boolean expressions as the first (for interesting
values of n) and is therefore faster.
My sloppy terminology came from the fact that the recursive branch
is the one which will be evaluated in all but the bottom-most
recursive call, therefore it is "most likely" and should be the
first one tested for.
Then force of habit took over, and I rewrote it to flatten out the
unnecessary nested test, which rendered the whole ordering issue
moot, as there remained only one boolean expression in the entire
function! Duhhh! (Note to self: When giving an example of a
principle, don't mix in another principle in a way that renders
the first one totally invisible!)
Sorry for any confusion I caused.
-jn-
