summation

APL-related discussions - a stream of APL consciousness.
Not sure where to start a discussion ? Here's the place to be
Forum rules
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !

summation

Postby Roger|Dyalog on Thu Mar 18, 2021 11:18 pm

Sum by Order of Magnitude

In a recent APL Chat Forum post on ⍟⍵, I observed that +/⍵ traverses its vector argument from left to right rather than the specified right to left. It meant that using +/⌽⍵ was more accurate than +/⍵ when ⍵ is a power series with rapidly declining terms.

Subsequently, I commented to Dyalog colleagues that for the most accuracy in +/⍵ you would sort ⍵ by magnitude, and then accumulate from smallest to largest. Adám Brudzewsky retorted that sorting by magnitude could still fail with lots of numbers of smaller orders of magnitude and a few numbers of larger orders of magnitude. He forwarded the function SumGroup devised by him and Marshall Lochbaum which demonstrates the effect:

      SumGroup ← (+/⊂∘⍋∘|⌷⊢){(+/⍵⌷⍨∘⊂⊢)⌸⌊10⍟1⌈|⍵}⍣≡

SumAsc ← +/ ∘ {⍵[⍋|⍵]}
SumDesc ← +/ ∘ {⍵[⍒|⍵]}

accompanied by the remark, Summing is hard™.

SumGroup groups the argument by order of magnitude (of absolute value) and sums each group separately, then repeats the process until there is only one number for each order of magnitude. The result obtains by a final summation in ascending magnitude.

      x0 ← 1 1e20 1 ¯1e20
x1 ← 1e16,10⍴1

⎕pp←18
SumAsc¨ x0 x1
0 10000000000000010
SumDesc¨ x0 x1
2 10000000000000000
SumGroup¨ x0 x1
2 10000000000000010

For x0 and x1, only SumGroup gave the mathematically correct result in both cases.

Improving SumGroup

In trying to understand SumGroup, I rephrased it step-by-step:

  • Judicious insertion of "redundant" spaces would improve readability.
  • (+/⊂∘⍋∘|⌷⊢) can be replaced by the equivalent SumAsc.
  • The left operand of the power operator, {(+/⍵⌷⍨∘⊂⊢)⌸⌊10⍟1⌈|⍵}, is equivalent to
    {(⌊10⍟1⌈|⍵){+/⍵}⌸⍵}. This latter formulation is more direct and more obviously grouping ⍵ by using ⌊10⍟1⌈|⍵ as keys.
  • Moreover, the computation of the order of magnitude is flawed in lumping together all numbers with magnitude less than 1 (what the 1⌈ does), and fails on arguments containing 0.
  • Finally, it turned out that the base of the logarithm does not matter greatly, as long as it is not a small number or a large number. Therefore, the base may as well be *1 and ⍟ alone (monadic ⍟) can be used.

Putting it all together:

      SumAsc    ← +/ ∘ {⍵[⍋|⍵]}
OrdMag ← ⌊ ∘ ⍟ ∘ (| + 0∘=)
SumGroup1 ← SumAsc (OrdMag {+/⍵}⌸ ⊢)⍣≡

SumGroup1 x0
2
SumGroup1 x1
10000000000000010

One advantage of having components is that they can be independently inspected and tested:

      x0
1 1E20 1 ¯1E20
OrdMag x0
0 46 0 46
(OrdMag {⊂⍵}⌸ ⊢) x0
┌───┬──────────┐
│1 1│1E20 ¯1E20│
└───┴──────────┘

x1
10000000000000000 1 1 1 1 1 1 1 1 1 1
OrdMag x1
36 0 0 0 0 0 0 0 0 0 0
(OrdMag {⊂⍵}⌸ ⊢) x1
┌─────────────────┬───────────────────┐
│10000000000000000│1 1 1 1 1 1 1 1 1 1│
└─────────────────┴───────────────────┘

t←(12⍴3 4)*(?12⍴10)
t
1 64 19683 256 9 262144 243 1 27 65536 6561 4096
OrdMag t
0 4 9 5 2 12 5 0 3 11 8 8
(OrdMag {⊂⍵}⌸ ⊢) t
┌───┬──┬─────┬───────┬─┬──────┬──┬─────┬─────────┐
│1 1│64│19683│256 243│9│262144│27│65536│6561 4096│
└───┴──┴─────┴───────┴─┴──────┴──┴─────┴─────────┘

(Misalignments in the display are due to defects in the APL Chat Forum software.)

Function Display

I have long been disappointed in the display of a "tacit definition":

      ]box on

SumGroup1
┌──────────────────┬──────────────────────────────────────────────┐
│┌─────┬─┬────────┐│┌────────────────────────────────────────┬─┬─┐│
││┌─┬─┐│∘│{⍵[⍋|⍵]}│││┌──────────────────────────┬─────────┬─┐│⍣│≡││
│││+│/││ │ ││││┌────────────────────┬─┬─┐│┌─────┬─┐│⊢││ │ ││
││└─┴─┘│ │ │││││┌───────────┬─┬────┐│∘│|│││{+/⍵}│⌸││ ││ │ ││
│└─────┴─┴────────┘│││││┌─┬─┬─────┐│∘│1 ∘⌈││ │ ││└─────┴─┘│ ││ │ ││
│ ││││││⌊│∘│10 ∘⍟││ │ ││ │ ││ │ ││ │ ││
│ │││││└─┴─┴─────┘│ │ ││ │ ││ │ ││ │ ││
│ ││││└───────────┴─┴────┘│ │ ││ │ ││ │ ││
│ │││└────────────────────┴─┴─┘│ │ ││ │ ││
│ ││└──────────────────────────┴─────────┴─┘│ │ ││
│ │└────────────────────────────────────────┴─┴─┘│
└──────────────────┴──────────────────────────────────────────────┘

The display discards information about the components which make up the overall computation. I wish there was an option that would provide one or both of the following:

      
┌──────┬──────────────────────────┐
│SumAsc│┌────────────────────┬─┬─┐│
│ ││┌──────┬─────────┬─┐│⍣│≡││
│ │││LogMag│┌─────┬─┐│⊢││ │ ││
│ │││ ││{+/⍵}│⌸││ ││ │ ││
│ │││ │└─────┴─┘│ ││ │ ││
│ ││└──────┴─────────┴─┘│ │ ││
│ │└────────────────────┴─┴─┘│
└──────┴──────────────────────────┘

SumAsc


┌─────┴─────┐
│ │
┌────┼────┐ ≡
OrdMag ⌸ ⊢

{+/⍵}
Roger|Dyalog
 
Posts: 238
Joined: Thu Jul 28, 2011 10:53 am

Return to APL Chat

Who is online

Users browsing this forum: No registered users and 1 guest