## 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

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 x10 10000000000000010      SumDesc¨  x0 x12 10000000000000000      SumGroup¨ x0 x12 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 x02      SumGroup1 x110000000000000010`

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

`      x01 1E20 1 ¯1E20      OrdMag x00 46 0 46      (OrdMag {⊂⍵}⌸ ⊢) x0┌───┬──────────┐│1 1│1E20 ¯1E20│└───┴──────────┘      x110000000000000000 1 1 1 1 1 1 1 1 1 1      OrdMag x136 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)      t1 64 19683 256 9 262144 243 1 27 65536 6561 4096      OrdMag t0 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: 236
Joined: Thu Jul 28, 2011 10:53 am