123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596 |
- #!/usr/bin/ruby
- # Simple implementation of Gaussian integers.
- # See also:
- # https://en.wikipedia.org/wiki/Gaussian_integer
- class Gaussian(a, b) { # represents: a + b*i
- method to_s {
- "Gaussian(#{a}, #{b})"
- }
- method reals {
- (a,b)
- }
- method ==(Gaussian c) {
- (a == c.a) && (b == c.b)
- }
- method conjugate {
- Gaussian(a, -b)
- }
- method norm {
- a*a + b*b
- }
- method add (Gaussian z) {
- var (c,d) = (z.a, z.b)
- Gaussian(a+c, b+d)
- }
- __CLASS__.alias_method(:add, '+')
- method sub (Gaussian z) {
- var (c,d) = (z.a, z.b)
- Gaussian(a-c, b-d)
- }
- __CLASS__.alias_method(:sub, '-')
- method mul (Gaussian z) {
- var (c,d) = (z.a, z.b)
- Gaussian(a*c - b*d, a*d + b*c)
- }
- __CLASS__.alias_method(:mul, '*')
- method mod (Number m) {
- Gaussian(a % m, b % m)
- }
- __CLASS__.alias_method(:mod, '%')
- method pow(Number n) {
- var x = self
- var c = Gaussian(1, 0)
- for bit in (n.digits(2)) {
- c *= x if bit
- x *= x
- }
- return c
- }
- __CLASS__.alias_method(:pow, '**')
- method powmod(Number n, Number m) {
- var x = self
- var c = Gaussian(1, 0)
- for bit in (n.digits(2)) {
- (c *= x) %= m if bit #=
- (x *= x) %= m #=
- }
- return c
- }
- }
- var a = Gaussian(3,4)**10
- var b = Gaussian(3,4).powmod(97, 1234)
- say a
- say b
- # Run some tests
- assert_eq([a.reals], [reals(Gauss(3,4)**10)])
- assert_eq([b.reals], [reals(Gauss(3,4).powmod(97, 1234))])
- assert_eq([reals(a+b)], [reals(Gauss(reals(a)) + Gauss(reals(b)))])
- assert_eq([reals(a-b)], [reals(Gauss(reals(a)) - Gauss(reals(b)))])
|