Math Methods

• Novel Methods of Integer Multiplication and Division
• Russian Peasent Multiplication and Exponentiation
• Division by a constant
• Difference between carry and overflow
• Increment: Pre vs Post and Inc vs Dec
• Square Roots
• FFT
• Radix conversions
• Techniques for exploiting the parallelism of bitwise operations [incl bit reversals, counting, and Morton keys] by Ron Gutman
• Expression Evaluation
• Units Conversions
• Knowing if a number is evenly divisable by a digit
• Fixed point math
• Matrix Math
• Approximations of Pi
• Gaussian functions
• @CRC and other Data Link Error Detection / Correction Methods

Delphi and BASM sample code

PIC specific math@ (including trigonometric functions sin(), arctan(), etc.), SX specific math@, Intel specific math@

Dr Dobbs Journal #271 pg 18 "A Conversation with William Kahan"  William Kahan "Formulas that are numerically stable are sometimes quite inelegant. Formulas that give you greater accuracy are sometimes full of cases, ugly cases.... F(x)=(sin x)/x  .... F(x)=(sin x)/x if x != 0 and F(0) = 1"

Have ex-mathematicians become dysfunctional?

See also:

• https://www.reenigne.org/blog/multiplying-faster-with-squares/ Multiplying Faster with Squares (Lookup). Because:
  (a+b)² = a² + b² + 2ab
  (a-b)² = a² + b² - 2ab
  Subtracting these gives:
  4ab = (a+b)² - (a-b)²
  Or:
  ab = (a+b)²/4 - (a-b)²/4
  which reduces the difficult parts from an x*y to an x²/4. With only one variable (and enough ram) lookup tables are suddenly back in frame. Because a-b and a+b are always both even or both odd, you only need one table. So if we keep in memory a table of x²/4 we can do a multiply with an add, two subtractions and two table lookups. The tables have a+b number of entries rather than a*b, but must hold values as large as a*b if the full range of possible output is to be supported.+
• http://floating-point-gui.de/ Floating point guide. Detailed explanation of how floating point works on binary systems and what can go wrong.+
• http://f3.to/portfolio/math/fastatan2.htm Fast ATAN2. if |X|>|Y| [(-b*x*y)/(x^2+ a*y^2) + c*sign(x)] else [-c*sign(x*y)= c*sign(x) + (b*x*y)/(y^2+a*x^2)] where a = 0.28088, b = 180/Pi, c = b/2*Pi
• http://www.eugeneleeslover.com/VIDEOS/fire_control_computer_1.html and part 2^ Shows how mechanical elements are used to compute answers. Understanding these methods helps to round out our understanding of mathematics.
• On-line CRC Concise Encyclopedia of Mathematics from Treasure-Troves.com
• Frequently Asked Questions in Mathematics from The Sci.Math FAQ Team. Editor: Alex López-Ortiz
• National Institute of Standards and Technology - Guide to Available Mathematical Software
• Netlib is a collection of mathematical software, papers, and databases
• http://farside.ph.utexas.edu/teaching/329/lectures/lectures.html Nice step by step tutorial in various aspects of computational physics
• http://integrals.wolfram.com/ Online integral evaluation with Mathematica.
• Scott Dattalo's
• SIN / COS approximations
  • CORDIC functions.
    • https://github.com/francisrstokes/githublog/blob/main/2024/5/10/cordic.md Why the CORDIC algorithm lives rent-free in my head.
      Precompute a table for tan(a), where a is in binary(ish) steps. So for i=0 to 15, each entry is actually atan(2**-i), converted to fixed point, so: atan(2**-i) * (1 << 16)
      To compute a sine or a cosine, convert the angle (e.g. 0.9152) to fixed point: 0.9152 * (1 << 16) = 59978

      #Initialize variables: 
      z = a * (1 << 16) #our input angle offset
      x = 39796         #the x point on a unit circle at 0 degrees in fixed point
      y = 0             #the y
      #The sign of z determines if we rotate clockwise or anti-clockwise.
      # and as we zero it out, we reach out answers
      
      for (i in range(0,sizeof(table)):
          if z >= 0:
              x_next = x - (y >> i)
              y_next = y + (x >> i)
              z -= table[i]
          else:
              x_next = x + (y >> i)
              y_next = y - (x >> i)
              z += table[i]
      x = x_next
      y = y_next
      

    • http://www.brouhaha.com/~eric/pic/sine.html (Implementing Sine on the PIC w/ source)
    • http://www.virtuaweb.com/picprog/links.html (link pg to all sorts of PIC code)
    • http://www.taygeta.com/cordic_refs.html (references to print, periodical and IEEE theory articles)
    • http://devil.ece.utexas.edu/original.html(references to print, periodical and IEEE theory articles)
    • http://ftp.arl.mil/ftp/pub/Gems/src/ (Source code related to the book "Graphics Gems" (editor, Andrew S. Glassner, published by Academic Press, Cambridge, MA, 1990, ISBN 0-12-286165-5, 833 pgs.)
    • http://devil.ece.utexas.edu/code.html
  • Scott Dattalo's Sine Waves
  • "ArcTan as Fast as You Can" by Dave Van Ess, has C code to implement arctan2(x,y) at various size/speed tradeoffs.
  • http://www.coranac.com/documents/arctangent/
• Randy Hyde's UCR Standard Library
  • Floating Point
• Reciprocal Division (BCD math)
• http://www.opferman.com/Computers/Math/index.shtml Toby Opferman's Math Tutorials For - Unit Circle & Trig Functions  * Linear Algerbra - Vectors - Matrices  * Calculus - Limits - Derivatives - Integrals (Anti-Derivatives)
• https://www.embeddedrelated.com/showarticle/760.php a few good algorithems. Russian Peasant Multiplication, The Single-Pole Low-Pass Filter, Welford's Method (And Friends), Topological Sort
• Part 5: Quadratic Extremum Interpolation and Chandrupatla's Method
• Part 6: Green’s Theorem and Swept-Area Detection
• http://babbage.cs.qc.edu/courses/cs341/IEEE-754.html Convert between decimal and IEEE-754 formats
• http://www.optonline.com/comptons/ceo/04099_A.html ROMAN NUMERALS
• http://www.mathcom.com/nafaq/index.html FAQ: Numerical Analysis & Associated Fields Resource Guide
• http://www.geocities.com/SiliconValley/2499/essays.html#TWOS Two's Complement and Binary Math

Books

• "Statistical Distributions" by NAJ Hastings and J.B.Peacock John Wiley 1974 ISBN 0-470-35889-0 This rare book is essential for anyone doing MonteCarlo simulations or using Random Number sequences. It is a collection of simple algorithms for generating random numbers with specific distributions given a simple random number generator with good first and second order distribution.

Math:

If you've got a basket with 3 oranges in it and you take 5 out, then you have to put 2 oranges in again in order for it to be empty. -- Peter Gutmann

Questions:

• https://www.poshenloh.com/quadraticdetail/ Simple way to factor quadratic equations of the form x² + Bx + C = 0.
  - Convert from Ax² + Bx + C = 0 by dividing all terms by A.
  - Find two numbers with sum -B and product C.
  - They will sum to -B if they are the average of B plus or minus some number: -B/2 +- u in other words: -B/2 = u and -B/2 = -u.
  - And (-B/2 + u)(-B/2 - u) = C or -B/2 - u² = C or u² = C - B/2
  - So u = sqrt(C - B/2).
  Summary: x^2 + Bx + C = 0. u = sqrt(C - B/2), r = -B/2 + u, and w = -B/2 - u. So (r + x)(w - x) = 0.
• taking the square (x^2) with PIC-specific math
• Nicolaas Gerhardus Scheepers of ElectronCraft asks:

  Hi there, I am having trouble with arithmetic in assembler. I want to do the following calculation:
  Y = ((X-Xmin)((Ymax-Ymin)/(Xmax-Xmin))) + Ymin This is a formula to scale a point between Xmax and Xmin to a point between Ymax and Ymin. The Y points is 8-bit but the X points can be up to 16-bit values. You can already see my problem because I cannot get any 16-bit divided by 16-bit algorith or for that matter 24-bit divided by 16-bit that replies with the fractional part. So I came up with the next formula to try and use a 16-bit divided by 8-bit number to give back fractions:
  Y = ((X-Xmin)(1/(Xmax-Xmin)/(Ymax-Ymin))) + Ymin But it just gets more complex as I go along. My second problem is that say I work out the division and now I must multiply the answer (which is fractional , how the hell do you do it with the fractional part. Do you first multiply both numbers so they are integer and then divide it again later with the same number or what. Am I even on the right track here or am I going bananas? Please help me I am now three months into the game and have learned a lot in a short space of time but the learning just seems to grow and not level out, not that I am complaining just a remark:-)

  Rearrange the formula so that the top and bottom of the fraction is kept seperate. What you really want is:
  
  Y = ((X-Xmin)(Ymax-Ymin) + Ymin(Xmax-Xmin)) over Xmax-Xmin.
  
  Now you can do the top and bottom seperatly. Multiplying by a fraction is a seperate job but can still be done without division. It is a good idea to reduce the fraction after each operation to prevent overflow. A method for doing that is available but I can't find it at the moment.
  
  Once you have the final answer, then you do the division.

See:

• /techref/microchip/mplab/sti-rs232/index.htm directory listing of 'H:\techref\microchip\mplab\sti-rs232'
• /techref/microchip/math/basic.htm PIC Microcontoller Basic Math Methods+

  .