**Kahan compensated summation algorithm and Neumaier variant summation algorithm, numerical analysis **
----
This page is under development. Comments are welcome, but please load any comments in the comments section at the bottom of the page. Please include your wiki MONIKER  in your comment with the same courtesy that I will give you. Its very hard to reply intelligibly without some background of the correspondent. Thanks,[gold]
----

<<TOC>>
----
**Introduction**
[gold] Here is some eTCL starter code for Kahan compensated summation algorithm and Neumaier variant summation algorithm. 
----
***Testcases Section***  

In planning any software, it is advisable to gather a number of testcases to check the results of the program. The math for the testcases can be checked by pasting statements in the TCL console. Aside from the TCL calculator display, when one presses the report button on the calculator, one will have console show access to the   capacity  functions (subroutines). 

**** Testcase 1 ****

**** Testcase 2 ****

**** Testcase 3 ****

**** Testcase 4 ****

----
***References:***
   *   [Primes]
   *   [Oneliner's Pie in the Sky] 
   *   [One Liners] 
----
**Appendix Code**

***appendix TCL programs and scripts ***
*** Kahan summation algorithm***
**Introduction**

[gold] Here is some TCL starter code for the Kahan summation algorithm.

The Kahan summation algorithm is used to counter round-off error with some effectiveness. Note: One won't see these (single precision) errors in normal TCL 8.6 use. The TCL script below uses <format %7.1f $inputs> to force single precision (sp) on expr and  math operator statements.  Expr from TCL 8.6 uses double precision inside its calculations and throws round off errors beyond normal sp use. However, this example of the kahan summation algorithm seems to be working correctly and can be compared to the gimmicked summation procs below.

Kahan, Neumaier, Babuska, and others developed balanced or compensated summation algorithms. Some balanced algorithms subtract the compensations from the summing terms as the terms accumulate. Other balanced algorithms model total compensation with a first, second, or nth order curve and subtract the total compensation from the total terms at the end. Second order balanced algorithms can require 50 percent more time, but could be worth it for more accuracy ( eg. function tables).

----

**Pseudocode Section**
======  
          # using  pseudocode for Kahan summation algorithm
          # possible problem instances for large angles n*360 degrees
          angle reduction degrees N50*740.00000000001 format %17.15f 280.000000000050930 
          angle reduction degrees N150*740.00000000001 format %17.15f 120.00000000016007
          trying to "cure" or slow growth of tail digits
          from round off digits, dp shown
         # kahan summation algorithm in pseudocode
          a(i)  = sequence of floating point numbers, a(i)>=3
          c = keeper result
          sum of floating point numbers
          loop following
          y = a(i) -c
          t = sum + y
          c = (t-sum)-y
          sum = t
         10000.0, 3.14159, 2.71828= (a + b) + c
          => single precision fp errors =>  10005.8.
          Kahan function a, b, c results in  10005.9
          ref normal TCL precision 12 or 17,
          expr is double precision inside calculations
          and not show these errors in sp.
          have to reproduce rd. error in single precision
          have to add fp format statements  
          correct for inputs of large angles and accumularted round off errors
     check_answer  (a + b) + c =?  a + ( b  + c ) (yes/no)
     set answers and printout with resulting values
======
----
***References:***
   * search keywords for "faster" trig approximations. 
   * sin cos tan trig series efficient approximation "nested polynomial" multiplication 
   * "Horner's method" "Horner's form" recursive telescoping 
   * Payne, Mary H.; Hanek, Robert N., Radian reduction for Large Angles,
   * implemented on Sparc 3, probably  C++ code and bit instructions
   * Argument reduction for huge arguments: Good to the Last Bit,
   * K. C. Ng, SunPro Works , March 24, 1992
   * SIAM J. Sci. Comput. Volume 31, Issue 1, pp. 189-224 (2008)
   * Accurate floating-point summation,  part 1: faithful rounding 
   * Siegfried M. Rump, Takeshi Ogita, and Shin Ichi Oishi 
   * Design and Implementation of a High Precision Arithmetic
   * with Rigorous Error Bounds,
   * Alexander Wittig,  MSUHEP-081126, December 2008
   * A generalized Kahan-Babuska Summation Algorithm,
   * Andreas Klein, April 21, 2005
   * implement a better summation algorithm, · Issue #199, · JuliaLang
   * Kahan's compensated summation algorithm,
   * William Kahan,  Further remarks on reducing truncation errors.
   * Comm. ACM, 8:40, 1965
   * Kahan and Babuska summation algorithm, Neumaier variant
   * A. Neumaier,  Rundungsfehleranalyse einiger Verfahren 
   * zur Summation endlicher Summen, in German
   * Math. Mechanik, 54:39–51, 1974.


----
*** Console  TCL script for angle reduction with kahan summation algorithm***
======
        # console program for angle reduction with kahan algorithm
        # pretty print from autoindent and ased editor
        # kahan summation algorithm into TCL
        # written on Windows XP on  TCL
        # working under TCL version 8.6
        # gold on TCL WIKI , 8jan2017, kahan_baby3
        package require Tk
        package require math::numtheory
        package require math::geometry
        package require math::constants
        package require math::bigfloat
        namespace path {::tcl::mathop ::tcl::mathfunc math::numtheory math::geometry math::constants math::bigfloat}
        #namespace import ::math::bigfloat::*
        set tclprecision 17
        #set tclprecision 8
        wm title . "angle reduction with kahan algorithm"
        console show
        proc summer_w_rd_error { lister } {
            set sum 0
            foreach number $lister {
                set sum [+ $sum [ format %7.1f $number ] ]
            }
            # statement to recreate single precision r. errors
            set sum [ format %7.1f $sum ]
            return $sum}
        proc summer_w_rd_expr { lister } {
            set sum 0
            foreach number $lister {
                set number [ format %7.1f $number ]
                set sum [ expr { $sum + $number } ]
            }
            # statement to recreate single precision r. errors
            set sum [ format %7.1f $sum ]
            return $sum}
        proc kahan_summation {lister} {
            set a {10000.0  3.14159  2.71828 }
            set b {9879879.88 6585497.99 875870989.54 765864865479.32 }
            set c { 1. 2. 3. }
            set compensation_keeper2  0
            set sum 0
            set counter 0
            set yaada2 0
            set term2 0
            foreach number $lister {
                set yaada2 [- $number $compensation_keeper2 ]
                set term2 [+ $sum $yaada2 ]
                set compensation_keeper2 [- [- $term2 $sum ] $yaada2 ]
                set sum $term2
                incr $counter}
            # statement to recreate single precision r. errors
            set sum [ format %7.1f $sum ]
            return $sum }
        proc degree_reduction {aa} {
            if { $aa > 360. } {
                while {$aa > 360.} {
                    set aa [- $aa 360.] }
                return $aa }
            if { $aa < -360. } {
                while {$aa < -360.} {
                    set aa [+ $aa 360.] }
                return $aa }
            return $aa }
        set kipper { 10000.0  3.14159  2.71828  }
        puts " normal expr summation, dp inside expr,format %7.1f [format %7.1f  [ expr { 10000.0 + 3.14159 + 2.71828 } 

] ]"
        puts " modify summer_w_rd_error, format %7.1f [ summer_w_rd_error $kipper ]  "
        puts " modify summer_w_rd_expr, format %7.1f [ summer_w_rd_expr $kipper ]  "
        puts " trial kahan summation, format %7.1f  [ kahan_summation $kipper  ]  "
        puts " angle reduction degrees 740.00000000001 [ degree_reduction 740.000000000001 ]  "
======
----
output
======
        # normal expr summation, dp inside expr,format %7.1f 10005.9
        # modify summer_w_rd_error, format %7.1f 10005.8  
        # modify summer_w_rd_expr, format %7.1f 10005.8  
        # trial kahan summation, format %7.1f  10005.9   
        # angle reduction degrees 740.00000000001 20.000000000001023,
        # due to round off error
        # angle reduction degrees N50*740.00000000001 format %17.15f 280.000000000050930 
        # angle reduction degrees N150*740.00000000001 format %17.15f 120.000000000160070
======
----
*** Console  TCL script for neumaier summation algorithm***
======
        # console program for neumaier summation algorithm
        # pretty print from autoindent and ased editor
        # neumaier algorithm summation algorithm into TCL
        # written on Windows XP on  TCL
        # working under TCL version 8.6
        # gold on TCL WIKI , 8jan2017,neumaier_baby5
        package require Tk
        package require math::numtheory
        package require math::geometry
        package require math::constants
        package require math::bigfloat
        namespace path {::tcl::mathop ::tcl::mathfunc math::numtheory math::geometry math::constants math::bigfloat}
        #namespace import ::math::bigfloat::*
        set tclprecision 17
        #set tclprecision 8
        wm title . " neumaier algorithm"
        console show
        #10000.0, 3.14159, 2.71828= (a + b) + c
        # (a + b) + c =?  a + (b + c)
        # => single precision fp errors =>  10005.8.
        # neumaier algorithm a, b, c results in  10005.9
        proc neumaier_summation {lister} {
            set a {10000.0  3.14159  2.71828 }
            set b {9879879.88 6585497.99 875870989.54 765864865479.32 }
            set c { 1. 2. 3. }
            set k { 1.0 +1.E100 1.0 -1.E100 }
            set keeper  0
            set sum 0
            set counter 0
            set term2 0
            set keeperx 0
            foreach number $lister {
                set term2 [+ $sum $number ]
                if { [abs $sum ] >= [abs $number ] } {
                    set keeper [+ [- $sum $term2 ] $number ] } else {
                    set keeper [+ [- $number $term2 ] $sum ] }
                set sum $term2
                set keeper2 $keeper
                set keeperx [+ $keeperx $keeper2 ]
                incr $counter}
            # statement to recreate single precision r. errors
            set sum [ format %7.1f $sum ]
            set keeper [ format %7.1f $keeper ]
            # puts " sum $sum keeper $keeper  sum+keeper  [+ $sum $keeper ] $sum $keeperx  [+ $sum $keeperx ]"
            return [ format %7.1f [+ $sum $keeperx ]] }
        set kipper { 10000.0  3.14159  2.71828  }
        set kipper { 1.0 +1.E16 1.0  -1.E16 }
        set kipper  { 1. 2. 3. }
        set kipper { 10000.0  3.14159  2.71828  }
        puts " normal expr summation, dp inside expr,format %7.1f sum { 10000.0  3.14159  2.71828  } [format %7.1f  [ expr { 10000.0 + 3.14159 + 2.71828 } ] ]"
        puts " normal expr summation, dp inside expr,format %7.1f sum {  +1.0 + +1.E15 + +1.0 + -1.E15  } [format %7.1f  [ expr { +1.0 + +1.E15 + +1.0 + -1.E15 } ] ]"
        puts " trial neumaier  summation, format %7.1f sum { 10000.0  3.14159  2.71828  } [ neumaier_summation $kipper  ]  "
        set kipper { 1.0 +1.E16 1.0  -1.E16 }
        puts " trial neumaier  summation, format %7.1f sum  { 1.0 +1.E16 1.0  -1.E16 } [ neumaier_summation $kipper  ]  "
        set kipper  { 1. 2. 3. }
        puts " trial neumaier  summation, format %7.1f sum  { 1. 2. 3. } = [ neumaier_summation $kipper  ]  "
        # normal expr summation, dp inside expr,format %7.1f sum { 10000.0  3.14159  2.71828  } 10005.9
        # normal expr summation, dp inside expr,format %7.1f sum {  +1.0 + +1.E15 + +1.0 + -1.E15  }     2.0
        # trial neumaier  summation, format %7.1f sum { 10000.0  3.14159  2.71828  } 10005.9  
        # trial neumaier  summation, format %7.1f sum  { 1.0 +1.E16 1.0  -1.E16 }     2.0  
        # trial neumaier  summation, format %7.1f sum  { 1. 2. 3. } =     6.0  
======

*** Console program used to build csv spreadsheet charts.***
----
[gold] This page is copyrighted under the TCL/TK license terms, [http://tcl.tk/software/tcltk/license.html%|%this license]. 

**Comments Section**

<<discussion>>
Please place any comments here, Thanks.

                              
<<categories>> Numerical Analysis | Toys | Calculator | Mathematics| Example| Toys and Games | Games | Application | GUI
----
<<categories>> Development | Concept| Algorithm | Spreadsheet