Books/MathForTheLayman/Polynomials and Number Systems

16: Polynomials and NUMBER SYSTEMS

16A. Ascending and descending order of exponents

In conventional mathematics, polynomials are sometimes expressed with the exponents in ascending order (beginning with zero), and sometimes in descending order (beginning with the largest exponent). Thus:

   ax0+bx1+cx2+dx3

   ax3+bx2+cx1+dx0

Descending order is commonly used in high school, but ascending order is more suitable in advanced math, because in truncated power series a “largest exponent” may not be clearly identified.

To compare these schemes we will define two functions called pa (for ascending order), and pd (for descending). The former is the function p. that we have used in earlier chapters, and the latter may be expressed in terms of it using the reversal function (|.) to reverse the order of the coefficients. Thus:

      pa=: p.
      pd=: |. on [ pa ]
      x=: 0 1 2 3 4 5
      1 2 3 pa x
   1 6 17 34 57 86
      1 2 3 pd x
   3 6 11 18 27 38
      1 2 3 pd 10
   123

The final example suggests that a descending polynomial with right argument 10 gives the value in decimal of the digits in the list of coefficients. In fact, the decimal number system (and number systems with bases other than ten) are “polynomial representations” of numbers, and we may find that schemes for multiplying polynomials lead to improved methods of multiplying multi-digit decimal numbers.

16B. Products of polynomials

The product of two polynomials c1 with p. and c2 with p. is itself a polynomial, whose coefficients can be computed from c1 and c2 by first forming their multiplication table. For example:

      c1=: 2 3 5
      c2=: 4 1 0 3
      c1 * table c2
   +-+---------+
   | | 4 1 0  3|
   +-+---------+
   |2| 8 2 0  6|
   |3|12 3 0  9|
   |5|20 5 0 15|
   +-+---------+

The coefficient 8 in the upper left corner is the coefficient of x^0 in the product polynomial, the elements of the next diagonal (2 12) are coefficients of x^1, the next diagonal has coefficients of x^2, and so on. The combined coefficients of successive powers may therefore be obtained by summing diagonals of the table to obtain c3=: 8 14 23 11 9 15. Thus:

      c3=: 8 14 23 11 9 15
      x=: 0 1 2 3 4 5
      (c1 p. x) * (c2 p. x)
   8 80 840 4928 18800 54528
      c3 p. x
   8 80 840 4928 18800 54528

In the expression f/. the oblique operator /. produces a function that applies f to each of the diagonals of a table argument. Thus:

      c1 */ c2
    8 2 0  6
   12 3 0  9
   20 5 0 15
      +//. c1 */ c2
   8 14 23 11 9 15
      c3 = +//. c1 */ c2
   1 1 1 1 1 1

We may therefore define a function pc to produce product coefficients as follows:

      pc=:  +//. on (*/)
      c1 pc c2
   8 14 23 11 9 15
      1 1 pc 1 1
   1 2 1
      1 1 pc 1 1 pc 1 1
   1 3 3 1

Similar reasoning will show that the same function pc produces coefficients for the product of descending polynomials. This may be tested as follows:

      c1 pd x
   5 10 19 32 49 70
      c2 pd x
   3 8 39 120 275 528
      (c1 pd x)*(c2 pd x)
   15 80 741 3840 13475 36960
      c3 pd x
   15 80 741 3840 13475 36960

16C. Multiplication of decimal numbers

The last result of Section 16A indicates that the result of c pd 10 is the decimal value of the number whose digits are the elements of the list c. Thus:

      c1=:  1 2 3
      c2=:  1 2 0 3
      (c1 pd 10),(c2 pd 10)
   123 1203

It follows that the elements of c1 pc c2 represent the product of the numbers 123 and 1203. Thus:

      ]c3=: c1 pc c2
   1 4 7 9 6 9
      c3 pd 10
   147969
      123*1203
   147969

Consequently, the product can be obtained by making the table c1 * table c2 and summing its diagonals:

      c1 * table c2
   +-+-------+
   | |1 2 0 3|
   +-+-------+
   |1|1 2 0 3|
   |2|2 4 0 6|
   |3|3 6 0 9|
   +-+-------+
      1,(+/2 2),(+/0 4 3),(+/3 0 6),(+/6 0),9
   1 4 7 9 6 9

However, these diagonal sums for other arguments may yield results greater than 9, and therefore themselves be multi-digit numbers. For example:

      c4=: 1 2 3 4 5 6 7
      c5=: 8 7 6 5 4
      ]c6=: c4 pc c5
   8 23 44 70 100 130 160 126 92 59 28
      c6 pd 10
   108214735818
      1234567*87654
   108214735818

The result c6 does correctly represent the product, but it is unsatisfactory in that its multi-digit elements cannot be simply squeezed together (as in 8234470100130160126925928) to produce the correct product.

An equivalent list of single digits can, however, be obtained by “carrying” all but the final digit to the next higher element, as illustrated in the following sequence:

      c6=: 8 23 44 70 100 130 160 126 92 59 28
      c7=: 8 23 44 70 100 130 160 126 92 61 8
      c8=: 8 23 44 70 100 130 160 126 98 1 8
      c9=: 8 23 44 70 100 130 160 135 8 1 8
      c10=: 8 23 44 70 100 130 173 5 8 1 8
      c11=: 8 23 44 70 100 147 3 5 8 1 8
      c12=: 8 23 44 70 114 7 3 5 8 1 8
      c13=: 8 23 44 81 4 7 3 5 8 1 8
      c14=: 8 23 52 1 4 7 3 5 8 1 8
      c15=: 8 28 2 1 4 7 3 5 8 1 8
      c16=: 10 8 2 1 4 7 3 5 8 1 8
      c17=: 1 0 8 2 1 4 7 3 5 8 1 8
      c6 pd 10
   108214735818
      c17 pd 10
   108214735818

Moreover, the entire normalization from c6 to c17 can be done easily by hand in a single process. In summary, multiplication of decimal numbers represented by the lists of digits d1 and d2 can be performed by hand by writing down the table d1 * table d2, summing the diagonals, and “normalizing” the results to single-digit elements (written together without spaces). This process may be compared with the commonly-taught scheme shown below:

        1234567
          87654
   ------------
        4938268
       6172835
      7407402
     8641969
    9876536
   ------------
   108214735818

In contrast to the three distinct steps of recording the multiplications in a table, summing its diagonals, and a final normalizion by carry, this conventional scheme combines multiplication and carry in each step of the production of each line, and again uses carrying in the final summation of the several lines.

Not only is this combined multiplication-and-carry more difficult to execute accurately, but the resulting record is almost impossible to check for possible errors except by repeating the entire process – a repetition that invites repetition of the same errors. 16D. Other bases S16D. Just as c pd 10 gives the decimal (or base-10) value of c as a weighted sum with weights of decreasing powers of 10, so c pd 8 gives the base-8 value, using powers of 8 as weights. For example:

      c1=: 1 2 3
      c2=: 1 2 0 3
      (c1 pd 8),(c2 pd 8)
   83 643
      ]c3=: c1 pc c2
   1 4 7 9 6 9
      c3 pd 8
   53369
      (c1 pd 8)*(c2 pd 8)
   53369

Again the result c3 can be normalized, this time to the range 0 to 7. This requires dividing by 8, “carrying” the integer quotient, and leaving the remainder. Thus:

      c3
   1 4 7 9 6 9
      1 4 7 9 7 1 pd 8
   53369
      1 4 8 1 7 1 pd 8
   53369
      1 5 0 1 7 1 pd 8
   53369

16E. Remainder, Divisibility, and Integer part S16E. The carrying process used in preceding sections made use of the remainder. For example, 8 divides into 24 exactly (that is, an integer number of times), but it divides 27 leaving a remainder of 3.

The remainder function is denoted by | and is illustrated by:

      | table i=: 1 2 3 4 5 6 7 8
   +-+---------------+
   | |1 2 3 4 5 6 7 8|
   +-+---------------+
   |1|0 0 0 0 0 0 0 0|
   |2|1 0 1 0 1 0 1 0|
   |3|1 2 0 1 2 0 1 2|
   |4|1 2 3 0 1 2 3 0|
   |5|1 2 3 4 0 1 2 3|
   |6|1 2 3 4 5 0 1 2|
   |7|1 2 3 4 5 6 0 1|
   |8|1 2 3 4 5 6 7 0|
   +-+---------------+

If the remainder d|n is zero, we say that n is divisible by d, as illustrated by the following divisibility table:

      =&0 on | table i
   +-+---------------+
   | |1 2 3 4 5 6 7 8|
   +-+---------------+
   |1|1 1 1 1 1 1 1 1|
   |2|0 1 0 1 0 1 0 1|
   |3|0 0 1 0 0 1 0 0|
   |4|0 0 0 1 0 0 0 1|
   |5|0 0 0 0 1 0 0 0|
   |6|0 0 0 0 0 1 0 0|
   |7|0 0 0 0 0 0 1 0|
   |8|0 0 0 0 0 0 0 1|
   +-+---------------+

The number n-d|n is divisible by d, and the result of the division d%~n-d|n is called the integer quotient. Thus:

      iq=: ([%~]-|)"0
      8 iq 22 23 24 25 26 27
   2 2 3 3 3 3
      iq table i
   +-+---------------+
   | |1 2 3 4 5 6 7 8|
   +-+---------------+
   |1|1 2 3 4 5 6 7 8|
   |2|0 1 1 2 2 3 3 4|
   |3|0 0 1 1 1 2 2 2|
   |4|0 0 0 1 1 1 1 2|
   |5|0 0 0 0 1 1 1 1|
   |6|0 0 0 0 0 1 1 1|
   |7|0 0 0 0 0 0 1 1|
   |8|0 0 0 0 0 0 0 1|
   +-+---------------+

The integer quotient can also be obtained by applying the integer part function <. to the result of division. For example:

      i%5
   0.2 0.4 0.6 0.8 1 1.2 1.4 1.6
      <.i%5
   0 0 0 0 1 1 1 1
      <. on (%~) table i
   +-+---------------+
   | |1 2 3 4 5 6 7 8|
   +-+---------------+
   |1|1 2 3 4 5 6 7 8|
   |2|0 1 1 2 2 3 3 4|
   |3|0 0 1 1 1 2 2 2|
   |4|0 0 0 1 1 1 1 2|
   |5|0 0 0 0 1 1 1 1|
   |6|0 0 0 0 0 1 1 1|
   |7|0 0 0 0 0 0 1 1|
   |8|0 0 0 0 0 0 0 1|
   +-+---------------+

16F. Notes

In his Chapter 6: The Dawn of nothing, Hogben provides an interesting discussion of number systems and the role of zero in their development. For example:

   Why this is necessarily true, is easy to see if we recall the Roman representation of 32, i.e. XXXII. If the Romans had written it in the form III II, there would have been no way of distinguishing it from 302, 320, 3,020, 3,200, etc. The one simple way of escape from this dilemma is to introduce a sign such as the Maya lozenge ..., a dot or a circle for the empty column of the abacus. We can then write 32, 302, 320, 3,020 as below:

   III II; IIIoII; III IIo; IIIoIIo

   ...If our base is b, we need only (b-1) other signs e.g. if b=10 the other signs we need are nine in all. We can then express any nameable number however great without enlarging our stock in trade.

   ...Its invention liberated the human intellect from the prison bars of the counting frame. The new script was a complete model of the mechanical process one performs with it. With a sign for the empty column, 'carrying over' on slate, paper or parchment is just as easy as carrying over on the abacus.

   ...In mediaeval Europe, the name for such rules was algorithms, a corruption of the name of a thirteenth century mathematician, spelled Al Khwarismi or Alkarismi.