APL Exercises 10
Arithmetic
⎕io←0 throughout.
10.0 Primality Testing
Write a function prime ⍵ which is 1 or 0 depending on whether non-negative integer ⍵ is a prime number. For example:
prime 1 0 prime 2 1 prime 9 0 prime¨ 10 10⍴⍳100 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0
10.1 Primes Less Than n
Write a function primes ⍵ using the sieve method which produces all the primes less than ⍵ . Use cmpx to compare the speed of primes n and (prime¨⍳n)/⍳n . For example:
primes 7 2 3 5 primes 50 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 (prime¨⍳50)/⍳50 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
10.2 Factoring
Write a function factor ⍵ which produces the prime factorization
of ⍵ ,
such that
factor 144 2 2 2 2 3 3 ×/ factor 144 144 ∧/ prime¨ factor 144 1 factor 1 factor 2 2
10.3 pco
Read about the pco function in http://dfns.dyalog.com/n_pco.htm and experiment with it.
)copy dfns pco pco ⍳7 2 3 5 7 11 13 17 1 pco ⍳10 0 0 1 1 0 1 0 1 0 0
G.H. Hardy states in
A
Mathematician’s Apology (chapter 14, page 23) that
the number of primes less than 1e9 is 50847478 .
Use pco to check whether this is correct.
10.4 GCD
Write a function ⍺ gcd ⍵ to compute the greatest common divisor of non-negative integers ⍺ and ⍵ using the Euclidean algorithm.
Write a function ⍺ egcd ⍵ to compute the GCD of ⍺ and ⍵ as coefficients of ⍺ and ⍵ , such that (⍺ gcd ⍵) = (⍺,⍵)+.×⍺ egcd ⍵ .
112 gcd 144 16 112 egcd 144 4 ¯3 112 144 +.× 112 egcd 144 16
10.5 Ring Extension
Z[√k] is the ring of integers Z extended with √k where k is not a perfect square. The elements of Z[√k] are ordered pairs (a,b) which can be interpreted as a+b×√k (a+b×k*0.5) .
Write a d-operator ⍺(⍺⍺ rplus)⍵ which does addition in Z[√⍺⍺].
3 4 (5 rplus) ¯2 7 1 11
Write a d-operator ⍺(⍺⍺ rtimes)⍵ which does multiplication in Z[√⍺⍺].
3 4 (5 rtimes) ¯2 7 134 13
Both of the above can be done using integer operations only.
10.6 Repeated Squaring I
Write a function ⍺ pow ⍵
that computes ⍺*⍵ using repeated
squaring. ⍺ is a number
and ⍵ a non-negative integer. Hint:
the binary representation of an integer n
obtains as 2⊥⍣¯1⊢n .
10.7 Repeated Squaring II
Write a d-operator ⍺(⍺⍺ rpow)⍵ that computes ⍺ raised to the power ⍵ using repeated squaring. ⍺ is in Z[√⍺⍺] and ⍵ is a non-negative integer.
⊃ (5 rtimes)/ 13 ⍴ ⊂ 1 1 2134016 954368 1 1 (5 rpow) 13 2134016 954368 1 ¯1 (5 rpow) 13 2134016 ¯954368
The last two expressions are key steps in an O(⍟n) computation of the n-th Fibonacci number using integer operations, using Binet’s formula.
