Help / JforC / Elementary Mathematics in J
>> << 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 y . 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 y :
_ 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 y :
/: 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 x :
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 y : 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