Help / JforC / Elementary Mathematics in J

From J Wiki
Jump to navigation Jump to search


>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help J for C Programmers


                                                                    32. Elementary Mathematics in J

Verbs for Mathematics

All the verbs have rank 0 0 .

x *. y   Lowest common multiple of x and y

x +. y   Greatest common divisor of x and y

x ! y    number of ways to choose x things from a population of y things.  More generally, (!y) % (!x) * (!y-x)

The verbs dyad e. (Member of) and dyad -. (set difference) are useful in working with sets.

Exact Arithmetic: Extended and Rational Numbers

In J, numbers are not limited to 32-bit integers or 64-bit floating point.  Extended integer and rational are atomic data types (like numeric, literal, and boxed) that allow representation of numbers exactly.  An extended integer constant is defined by a sequence of digits with the letter x appended; a rational constant is two strings of digits (numerator and denominator) separated by the letter r; examples are 123x and 4r5 .

The various representations of numbers in J have a priority order:

boolean (low) - integer - extended integer - rational - floating point - complex (high)

When a dyadic arithmetic operation is performed on operands of different priorities, the lower-priority operand is converted to the higher-priority representation.  The simplest example arises in a list constant:

   12345678901234567890 4r5
12345678901234567890 4r5

The integer was made into a rational number so it keeps its precision.

   3.0 4r5
3 0.8

The floating-point constant forces the rational number to floating point.

   2 * 3r4
3r2

The operation was performed on rational operands with a rational result.

Note that the priority order is not an order of precision.  Exact precision, given by extended-integer or rational representation, has lower priority than floating-point precision, which is inexact.

Results of verbs are given a higher-priority representation if necessary.  Results of non-extended integer computations that do not fit in a standard integer are converted to floating-point, not extended integer, for performance reasons.

   %: 4r9
2r3
   %: 5r9
0.745356
   2^32
4.29497e9

Changing Precision: Monad and Dyad x:

Explicit conversions between extended/rational and floating-point can be performed by the infinite-rank verb x: x: y converts floating-point y to rational or integer y to extended integer.  The inverse, x:^:_1 y, converts in the other direction.

A rational number can be split into numerator and denominator by 2 x: y (rank 0):

   2 x: 1r3 5
1 3
5 1

Understanding Precision

The first thing to remember is that numeric constants containing a decimal point produce 64-bit floating-point numbers, not rational numbers, no matter how many decimal places you provide:

   0j20 ": 1.234567890123456789
1.23456789012345670000

Floating-point numbers have at most about 16 decimal digits of precision; the additional digits were lost.

If you want an exact-precision fraction, specify a rational constant or create one by dividing exact-precision integers:

   1234567890123456789r1000000000000000000
1234567890123456789r1000000000000000000
   1234567890123456789x % 1000000000000000000x
1234567890123456789r1000000000000000000
   0j20 ": 1234567890123456789r1000000000000000000
1.23456789012345678900  NB. full precision

To make a calculation use exact precision, you must make part of it exact-precision, and make sure that no floating-point values appear.  This means that you must move into the exact-precision domain before you produce a fraction or an integer that will not fit exactly into a machine integer (which is 32 or 64 bits depending on your machine).

   22 ": 9 ^ 20
  12157665459056929000

The result did not fit into a 64-bit float, so significance was lost...

   22 ": 1 + 9 ^ 20
  12157665459056929000

...with the usual floating-point effects: adding 1 does not change the value.

   22 ": 1x + 9 ^ 20
  12157665459056929000

Making the 1 extended doesn't help, because 9 ^ 20 has already produced a floating-point value.

   22 ": 9 ^ 20x
  12157665459056928801

With the 20 extended, all the computations are done in exact precision.

   22 ": 1 + 9 ^ 20x
  12157665459056928802

Some verbs, such as %: (square root) and ^. (natural logarithm), may produce non-integral results.  The interpreter will represent the result of such a verb as an exact-precision number if possible, but if the result has no exact representation it will revert to floating-point:

   %: 1r4
1r2
   %: 1r5
0.447214

There is no way to get an exact result from %: 2, but it is possible, with some effort, to get a result with more precision than is provided by a floating-point number.  The key is the idiom <.@v (or >.@v), where v is the verb you want to apply.  When you code <.@v, the interpreter knows you are interested in only the integer part of the result, and if the operand is exact-precision, the interpreter will evaluate the integer part of the result exactly.  By adjusting the size of the integer part, you can end up with high-precision fractions.

   0j20 ": t =. %: 2x
1.41421356237309510000

%: 2x is a floating-point value, limited as usual to 16 decimal places or so.

   0j20 ": *: t
2.00000000000000040000

Imprecise in the 17th place, as expected..

   0j20 ": t =. (10^20x) %~ <.@%: (10^40x) * 2x
1.41421356237309504880

Here we scaled 2 up with 40 low-order decimal zeros; then took the square root, using <.@v to ensure that the entire integer result is accurate; then scaled back down.

   0j20 ": *: t
2.00000000000000000000

The result is more accurate.

Factors and Primes: p: and q:

p: y gives the value of the yth prime number.  Prime number 0 is 2.

x p: y answers questions about the primality or factors of x is a control variable that tells what you are interested in.

x

Meaning of x p: y

Equivalents

_1

number of primes smaller than y

p:^:_1 y

0

0 if y is prime, 1 otherwise

 

1

1 if y is prime, 0 otherwise

 

2

exponents in the prime factorization of y

__ q: y

3

the prime factors of y

q: y

4

the smallest prime larger than y

 

Tests for the primality of values of y larger than 2^31 are tested using the probabilistic Miller-Rabin algorithm.

x q: y (rank 0) with positive x is the first x items (all items, if x is _) in the list of exponents in the prime factorization of :

   _ q: 700
2 0 2 1
   */ (p: 0 1 2 3) ^ 2 0 2 1
700

x q: y with negative x returns a 2-row table.  The second row is the nonzero items of (|x) q: y (i. e. the nonzero exponents in the prime factorization); the first row is the corresponding prime numbers:

   __ q: 700
2 5 7
2 2 1

Permutations: A. and C.

In the direct representation of a permutation p each item i{p of the permutation vector indicates the item number that moves to position i when the permutation is applied.  Applying the permutation in the direct form is as simple as writing p{y .

The standard cycle representation of a permutation gives the permutation as a list of cycles (sets of elements that are replaced by other elements of the set).  The standard cycle form is a list of boxes, one for each cycle, with each cycle starting with the largest element and the cycles in ascending order of largest element.

Monad C. y (rank 1) converts between direct and standard-cycle representations of the permutation :

   /: 3 1 4 1 5 9
1 3 0 2 4 5
   C. /: 3 1 4 1 5 9
+-------+-+-+
|3 2 0 1|4|5|
+-------+-+-+
   C. C. /: 3 1 4 1 5 9
1 3 0 2 4 5

x C. y (rank 1 _) permutes the items of y according to the permutation x which may be in either standard-cycle or direct form; other nonstandard forms are also supported as described in the Dictionary.

There are !n possible permutations on n items, so it is possible to give each one a number between 0 and <:!n .  Imagine the table of all possible permutations in lexicographic order; the anagram index of a permutation is its index in that table.  A. y (rank 0) gives the anagram index for the permutation y, which may be in either direct or standard-cycle form.  x A. y (rank 0 _) permutes the items of y according to the permutation whose anagram index is :

   a =. /: 3 1 4 1 5 9
   A. a
168
   a C. 1 2 3 4 5 6
2 4 1 3 5 6
   168 A. 1 2 3 4 5 6
2 4 1 3 5 6

The monad C.!.2 y gives the parity of : 1 if an even number of pairwise exchanges are needed to convert y to the identity permutation i.#y, _1 if an odd number are needed, 0 if y is not a permutation.


>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help J for C Programmers