So my nephew and I came up with different algorithms for working out a probability problem. Here's both of them in a script and the output: #!/bin/zsh setopt force_float integer level= typeset -F term= typeset -F numerator= typeset -F denominator= for ((level=1; level<23; level++)); do # Ray: numerator= for ((term=1; term <= level; term++)); do (( numerator += (level**(term - 1)) * (level - 1)**(level - term) )) done (( denominator = level**level )) printf "%.0f / %.0f \n" "$(( numerator ))" "$(( denominator ))" # Brett: numerator=1 for ((term=1; term < level; term++)); do (( numerator = numerator * (level - 1) + level**term )) done (( denominator = level**level )) printf "%.0f / %.0f \n" "$(( numerator ))" "$(( denominator ))" done ========================================= 1 / 1 1 / 1 3 / 4 3 / 4 19 / 27 19 / 27 175 / 256 175 / 256 2101 / 3125 2101 / 3125 31031 / 46656 31031 / 46656 543607 / 823543 543607 / 823543 11012415 / 16777216 11012415 / 16777216 253202761 / 387420489 253202761 / 387420489 6513215599 / 10000000000 6513215599 / 10000000000 185311670611 / 285311670611 185311670611 / 285311670611 5777672071535 / 8916100448256 5777672071535 / 8916100448256 195881901213181 / 302875106592253 195881901213181 / 302875106592253 7174630439858727 / 11112006825558016 7174630439858727 / 11112006825558016 282325794823047136 / 437893890380859392 282325794823047136 / 437893890380859392 11878335717996660736 / 18446744073709551616 11878335717996660736 / 18446744073709551616 532092356706984001536 / 827240261886336827392 532092356706984001536 / 827240261886336827392 25283323623228810723328 / 39346408075296541507584 25283323623228810723328 / 39346408075296541507584 1270184310304975863414784 / 1978419655660313627328512 1270184310304975863414784 / 1978419655660313627328512 67267626542454044570419200 / 104857600000000000000000000 67267626542454044570419200 / 104857600000000000000000000 3745435018385981790358601728 / 5842587018385982340114415616 3745435018385981790358601728 / 5842587018385982340114415616 218733549978113966650274349056 / 341427877364219559508793360384 218733549978113931465902260224 / 341427877364219559508793360384 # ^ Ooops! ... both work. But look at the last pair. The two diverge in the numerator, why is that? If there was some rounding of fractions or something I'd understand that an error would eventually pop up, but there's no divisions, only whole number integer arithmetic. It's puzzling that the two are perfect until the numbers get big, but it's not close to overflow and even then the denominator is bigger and has no issue. Obviously no bridges are going to fall down for an error in the 17th digit, but I'm curious.
> On Mar 25, 2021, at 11:52 AM, Ray Andrews <rayandrews@eastlink.ca> wrote: > > It's puzzling that the two are perfect until the numbers get big, but it's not close to overflow and even then the denominator is bigger and has no issue. Obviously no bridges are going to fall down for an error in the 17th digit, but I'm curious. The bad news is that *all* your figures -- your numerators, Brett's numerators, and the denominators -- are actually incorrect for level=15 and higher. The good news is that it's not your algorithms per se. Below are the results of interleaving your original script with lookalike Python implementations that produce correct figures. (For evidence of correctness, here's a concordant Wolfram Language implementation: https://www.wolframcloud.com/obj/6281a1a4-1094-4aac-b10b-4139b6444d6e) vq % zsh --version zsh 5.8 (x86_64-apple-darwin18.7.0) % python3.9 -V Python 3.9.2 % cat /tmp/demo.zsh #!/bin/zsh setopt force_float integer level= typeset -F term= typeset -F numerator= typeset -F denominator= for ((level=1; level<23; level++)); do numerator= for ((term=1; term <= level; term++)); do (( numerator += (level**(term - 1)) * (level - 1)**(level - term) )) done (( denominator = level**level )) printf 'L%-2d %-25s %.0f\n' $level 'Ray (zsh):' "$(( numerator ))" python3.9 - $level <<\EOF import sys level = int(sys.argv[1]) numerator = 0 for term in range(1, level+1): numerator += (level**(term - 1)) * (level - 1)**(level - term) denominator = level**level print(f"L{level:<2} {'Ray (Python 3.9):':25} {numerator}") EOF numerator=1 for ((term=1; term < level; term++)); do (( numerator = numerator * (level - 1) + level**term )) done (( denominator = level**level )) printf 'L%-2d %-25s %.0f\n' level 'Brett (zsh):' "$(( numerator ))" python3.9 - $level <<\EOF import sys level = int(sys.argv[1]) numerator = 1 for term in range(1, level): numerator = numerator * (level - 1) + level**term denominator = level**level print(f"L{level:<2} {'Brett (Python 3.9):':25} {numerator}") EOF printf 'L%-2d %-25s %.0f\n' \ $level 'denominator (zsh):' "$(( denominator ))" python3.9 - $level <<\EOF import sys level = int(sys.argv[1]) print(f"L{level:<2} denominator (Python 3.9): {level**level}") EOF done % zsh /tmp/demo.zsh L1 Ray (zsh): 1 L1 Ray (Python 3.9): 1 L1 Brett (zsh): 1 L1 Brett (Python 3.9): 1 L1 denominator (zsh): 1 L1 denominator (Python 3.9): 1 L2 Ray (zsh): 3 L2 Ray (Python 3.9): 3 L2 Brett (zsh): 3 L2 Brett (Python 3.9): 3 L2 denominator (zsh): 4 L2 denominator (Python 3.9): 4 L3 Ray (zsh): 19 L3 Ray (Python 3.9): 19 L3 Brett (zsh): 19 L3 Brett (Python 3.9): 19 L3 denominator (zsh): 27 L3 denominator (Python 3.9): 27 L4 Ray (zsh): 175 L4 Ray (Python 3.9): 175 L4 Brett (zsh): 175 L4 Brett (Python 3.9): 175 L4 denominator (zsh): 256 L4 denominator (Python 3.9): 256 L5 Ray (zsh): 2101 L5 Ray (Python 3.9): 2101 L5 Brett (zsh): 2101 L5 Brett (Python 3.9): 2101 L5 denominator (zsh): 3125 L5 denominator (Python 3.9): 3125 L6 Ray (zsh): 31031 L6 Ray (Python 3.9): 31031 L6 Brett (zsh): 31031 L6 Brett (Python 3.9): 31031 L6 denominator (zsh): 46656 L6 denominator (Python 3.9): 46656 L7 Ray (zsh): 543607 L7 Ray (Python 3.9): 543607 L7 Brett (zsh): 543607 L7 Brett (Python 3.9): 543607 L7 denominator (zsh): 823543 L7 denominator (Python 3.9): 823543 L8 Ray (zsh): 11012415 L8 Ray (Python 3.9): 11012415 L8 Brett (zsh): 11012415 L8 Brett (Python 3.9): 11012415 L8 denominator (zsh): 16777216 L8 denominator (Python 3.9): 16777216 L9 Ray (zsh): 253202761 L9 Ray (Python 3.9): 253202761 L9 Brett (zsh): 253202761 L9 Brett (Python 3.9): 253202761 L9 denominator (zsh): 387420489 L9 denominator (Python 3.9): 387420489 L10 Ray (zsh): 6513215599 L10 Ray (Python 3.9): 6513215599 L10 Brett (zsh): 6513215599 L10 Brett (Python 3.9): 6513215599 L10 denominator (zsh): 10000000000 L10 denominator (Python 3.9): 10000000000 L11 Ray (zsh): 185311670611 L11 Ray (Python 3.9): 185311670611 L11 Brett (zsh): 185311670611 L11 Brett (Python 3.9): 185311670611 L11 denominator (zsh): 285311670611 L11 denominator (Python 3.9): 285311670611 L12 Ray (zsh): 5777672071535 L12 Ray (Python 3.9): 5777672071535 L12 Brett (zsh): 5777672071535 L12 Brett (Python 3.9): 5777672071535 L12 denominator (zsh): 8916100448256 L12 denominator (Python 3.9): 8916100448256 L13 Ray (zsh): 195881901213181 L13 Ray (Python 3.9): 195881901213181 L13 Brett (zsh): 195881901213181 L13 Brett (Python 3.9): 195881901213181 L13 denominator (zsh): 302875106592253 L13 denominator (Python 3.9): 302875106592253 L14 Ray (zsh): 7174630439858727 L14 Ray (Python 3.9): 7174630439858727 L14 Brett (zsh): 7174630439858727 L14 Brett (Python 3.9): 7174630439858727 L14 denominator (zsh): 11112006825558016 L14 denominator (Python 3.9): 11112006825558016 L15 Ray (zsh): 282325794823047136 L15 Ray (Python 3.9): 282325794823047151 L15 Brett (zsh): 282325794823047136 L15 Brett (Python 3.9): 282325794823047151 L15 denominator (zsh): 437893890380859392 L15 denominator (Python 3.9): 437893890380859375 L16 Ray (zsh): 11878335717996660736 L16 Ray (Python 3.9): 11878335717996660991 L16 Brett (zsh): 11878335717996660736 L16 Brett (Python 3.9): 11878335717996660991 L16 denominator (zsh): 18446744073709551616 L16 denominator (Python 3.9): 18446744073709551616 L17 Ray (zsh): 532092356706984001536 L17 Ray (Python 3.9): 532092356706983938321 L17 Brett (zsh): 532092356706984001536 L17 Brett (Python 3.9): 532092356706983938321 L17 denominator (zsh): 827240261886336827392 L17 denominator (Python 3.9): 827240261886336764177 L18 Ray (zsh): 25283323623228810723328 L18 Ray (Python 3.9): 25283323623228812584415 L18 Brett (zsh): 25283323623228810723328 L18 Brett (Python 3.9): 25283323623228812584415 L18 denominator (zsh): 39346408075296541507584 L18 denominator (Python 3.9): 39346408075296537575424 L19 Ray (zsh): 1270184310304975863414784 L19 Ray (Python 3.9): 1270184310304975912766347 L19 Brett (zsh): 1270184310304975863414784 L19 Brett (Python 3.9): 1270184310304975912766347 L19 denominator (zsh): 1978419655660313627328512 L19 denominator (Python 3.9): 1978419655660313589123979 L20 Ray (zsh): 67267626542454044570419200 L20 Ray (Python 3.9): 67267626542454041806644399 L20 Brett (zsh): 67267626542454044570419200 L20 Brett (Python 3.9): 67267626542454041806644399 L20 denominator (zsh): 104857600000000000000000000 L20 denominator (Python 3.9): 104857600000000000000000000 L21 Ray (zsh): 3745435018385981790358601728 L21 Ray (Python 3.9): 3745435018385982521381124421 L21 Brett (zsh): 3745435018385981790358601728 L21 Brett (Python 3.9): 3745435018385982521381124421 L21 denominator (zsh): 5842587018385982340114415616 L21 denominator (Python 3.9): 5842587018385982521381124421 L22 Ray (zsh): 218733549978113966650274349056 L22 Ray (Python 3.9): 218733549978113924447643110743 L22 Brett (zsh): 218733549978113931465902260224 L22 Brett (Python 3.9): 218733549978113924447643110743 L22 denominator (zsh): 341427877364219559508793360384 L22 denominator (Python 3.9): 341427877364219557396646723584
On 2021-03-25 1:40 p.m., Lawrence Velázquez wrote:
>
> The bad news is that *all* your figures -- your numerators, Brett's
> numerators, and the denominators -- are actually incorrect for
> level=15 and higher.
Sheesh, what gives? Seems no accuracy beyond 15 digits? Thanks for
the sleuthing!
[-- Attachment #1: Type: text/plain, Size: 770 bytes --] On Thu, Mar 25, 2021 at 11:44 PM Ray Andrews <rayandrews@eastlink.ca> wrote: > On 2021-03-25 1:40 p.m., Lawrence Velázquez wrote: > > > > The bad news is that *all* your figures -- your numerators, Brett's > > numerators, and the denominators -- are actually incorrect for > > level=15 and higher. > Sheesh, what gives? Seems no accuracy beyond 15 digits? > Indeed. 64-bit floating point numbers usually have 15.95 decimal digits of precision. Depending on the compiler and how you write your code, you might get higher precision but in practice many projects turn this off because having borderline non-deterministic results of computation sucks. This isn't specific to zsh. Floating numbers are nowadays the same everywhere (IEEE 754). Roman. [-- Attachment #2: Type: text/html, Size: 1120 bytes --]
On 2021-03-25 3:54 p.m., Roman Perepelitsa wrote:
> On Thu, Mar 25, 2021 at 11:44 PM Ray Andrews <rayandrews@eastlink.ca
> <mailto:rayandrews@eastlink.ca>> wrote:
>
> On 2021-03-25 1:40 p.m., Lawrence Velázquez wrote:
> >
> > The bad news is that *all* your figures -- your numerators, Brett's
> > numerators, and the denominators -- are actually incorrect for
> > level=15 and higher.
> Sheesh, what gives? Seems no accuracy beyond 15 digits?
>
>
> Indeed. 64-bit floating point numbers usually have 15.95 decimal
> digits of precision. Depending on the compiler and how you write your
> code, you might get higher precision but in practice many projects
> turn this off because having borderline non-deterministic results of
> computation sucks.
That's for sure. I'd rather the result was truncated. Why show
garbage? Nuts, why compute garbage?
Ray Andrews wrote:
> printf "%.0f / %.0f \n" "$(( numerator ))" "$(( denominator ))"
Where you use %f, %d etc. the printf parameters are evaluated in math
context so there's no need to convert via ASCII decimal representation
with "$(( … ))". You can just do:
printf "%.0f / %.0f \n" numerator denominator
or even
printf "%.0f / %.0f \n" numerator 'level**level'
That feature is particular to zsh's printf. It doesn't really get you
much further with this particular script. Arbitrary precision (bignums)
might have been appropriate in the case of the shell rather than floats
but floats are what we have.
Oliver
On 2021-03-25 5:16 p.m., Oliver Kiddle wrote: > Ray Andrews wrote: >> printf "%.0f / %.0f \n" "$(( numerator ))" "$(( denominator ))" > Where you use %f, %d etc. the printf parameters are evaluated in math > context so there's no need to convert via ASCII decimal representation > with "$(( … ))". You can just do: > > printf "%.0f / %.0f \n" numerator denominator Thanks. Actually I just figured that out myself. > e of the shell rather than floats > but floats are what we have. But why do we let them spew out garbage? Just now I experimented with " %d " as the output specifier and it very politely goes obviously wrong at level 16 so you know it's reached the end of its rope, but the floats just keep on floating way into nonsense. Very unhygienic.
[-- Attachment #1: Type: text/plain, Size: 460 bytes --] On Fri, Mar 26, 2021 at 1:38 AM Ray Andrews <rayandrews@eastlink.ca> wrote: > On 2021-03-25 5:16 p.m., Oliver Kiddle wrote: > > but floats are what we have. > But why do we let them spew out garbage? > Maybe this will help: https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html Understanding how floating point numbers work is very useful. It's virtually mandatory when writing numerical computation code. None of this is specific to zsh. Roman. [-- Attachment #2: Type: text/html, Size: 884 bytes --]
On 2021-03-26 3:35 a.m., Roman Perepelitsa wrote: > > Maybe this will help: > https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html > <https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html> Good to know! Seriously, I've often wondered what really goes on in a calculator. Ok, for now I know that zsh and probably everybody else will compute endless reams of garbage if you let it. Here's my algorithm with the outer 'for' loop increasing exponentially: Ray's Algorithm fractional: Level: 1: win: 1 / 1 Level: 10: win: 6513215599 / 10000000000 Level: 100: win: 6339676587267708385630188881009247729557115329795338127068495312693456362833186743509112446 7602830066897486524892436064552875964380756727929631216242621046676674030227216977589219271 483398068889452544 / 9999999999999999697331222125103616594745032754550236264824175095034684843555407553419633840 4706251868027512415973882408182135734368278484639385041047239877871023591066789981811181813 306167128854888448 Level: 1000: win: inf / inf Level: 10000: win: inf / inf Level: 100000: win: inf / inf Level: 1000000: win: inf / inf .... I'm asking why the 'Level: 100' result isn't just aborted after 15 digits given that all the rest is garbage? > > Understanding how floating point numbers work is very useful. It's > virtually mandatory when writing numerical computation code. None of > this is specific to zsh. Amen! Seriously, I had no idea this sort of thing was permitted. Thanks Roman. For now I'll use ' %d' for output and at least I'll know when things turn to mud, there must be limits to precision and there must be overflow at some point. (But of course we hafta use floats if there's a division anywhere, just don't use them for display.)
[-- Attachment #1: Type: text/plain, Size: 927 bytes --] On Fri, Mar 26, 2021 at 3:36 PM Ray Andrews <rayandrews@eastlink.ca> wrote: > > Ok, for now I know that zsh and probably everybody else will compute > endless reams of garbage if you let it. Computers do what you ask them to do. The problem is that you are asking it to do one thing while expecting something else. When you start programming, you can think of "integer" and "float" variables as mathematical entities that behave like numbers (integer and real respectively). Once you get more experiences you need to realize that this is false. The sooner you do this, the more effective you'll be. .... I'm asking why the 'Level: 100' result isn't just aborted after 15 > digits given that all the rest is garbage? > Aborted based on which condition? If the result of an operation is not representable exactly in a double? If so, then even `1. / 10` would abort because the real number 0.1 is not representable. Roman. [-- Attachment #2: Type: text/html, Size: 1475 bytes --]
On 2021-03-26 7:49 a.m., Roman Perepelitsa wrote: > > Aborted based on which condition? If the result of an operation is not > representable exactly in a double? If so, then even `1. / 10` would > abort because the real number 0.1 is not representable. > Ha! You have a point there! The article you linked talked about some of these issues, but surely in my case it's simply a plain fact that no decimal past 15 can be accurate ever? Perhaps in practice this is not so easy to distinguish but we used to end rounding errors with that (what's it called?) the 'S' on it's side, the 'approximation' symbol. Anyway, it's easy for me to preach since I don't have to figure out how this would work in practice. It's easy to talk about but perhaps not so easy to code. For now I'm awake to the issue: no accuracy past 15 digits. > Roman.
> On Mar 25, 2021, at 7:57 PM, Ray Andrews <rayandrews@eastlink.ca> wrote: > > That's for sure. I'd rather the result was truncated. Why show > garbage? > On Mar 25, 2021, at 8:37 PM, Ray Andrews <rayandrews@eastlink.ca> wrote: > > But why do we let them spew out garbage? Just now I experimented > with " %d " as the output specifier and it very politely goes > obviously wrong at level 16 so you know it's reached the end of its > rope, but the floats just keep on floating way into nonsense. > On Mar 26, 2021, at 10:36 AM, Ray Andrews <rayandrews@eastlink.ca> wrote: > > I'm asking why the 'Level: 100' result isn't just aborted after 15 > digits given that all the rest is garbage? > On Mar 26, 2021, at 11:35 AM, Ray Andrews <rayandrews@eastlink.ca> wrote: > > surely in my case it's simply a plain fact that no decimal past 15 > can be accurate ever? zsh already knows how to indicate an appropriate degree of precision. You are FORCING it to spew garbage. % cat /tmp/demo.zsh; echo python3.9 <<\EOF print(f"{'Python:':<11} {22**22}") EOF printf '%-10s %s\n' 'zsh (%s):' $(( 22.0**22 )) printf '%s %.0f\n' 'zsh (%.0f):' '22.0**22' % zsh /tmp/demo.zsh Python: 341427877364219557396646723584 zsh (%s): 3.4142787736421956e+29 zsh (%.0f): 341427877364219559508793360384 vq
On 2021-03-26 10:09 a.m., Lawrence Velázquez wrote:
>
> printf '%s %.0f\n' 'zsh (%.0f):' '22.0**22'
>
Interesting I was formatting with the same ' %.0f ' but getting the ca.
200 character output. ' %s ' is no improvement. How do I get her to
trim it down? Mind, ' %d ' seemed just fine. I don't think much more
needs to be said about this.
> On Mar 26, 2021, at 5:45 PM, Ray Andrews <rayandrews@eastlink.ca> wrote: > > On 2021-03-26 10:09 a.m., Lawrence Velázquez wrote: >> >> printf '%s %.0f\n' 'zsh (%.0f):' '22.0**22' >> > Interesting I was formatting with the same ' %.0f ' but getting the ca. 200 character output. ' %s ' is no improvement. 22^22 is not 200 digits long. We're not talking about the same input. % cat /tmp/demo.zsh python3.9 <<\EOF print(f"{'Python:':<11} {100**100}") EOF printf '%-10s %s\n' 'zsh (%s):' $(( 100.0**100 )) printf '%s %.0f\n' 'zsh (%.0f):' '100.0**100' % zsh /tmp/demo.zsh Python: 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 zsh (%s): 9.9999999999999997e+199 zsh (%.0f): 99999999999999996973312221251036165947450327545502362648241750950346848435554075534196338404706251868027512415973882408182135734368278484639385041047239877871023591066789981811181813306167128854888448 > How do I get her to trim it down? *it vq