Skip to content

Instantly share code, notes, and snippets.

@grondilu
Created December 12, 2012 22:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save grondilu/4272252 to your computer and use it in GitHub Desktop.
Save grondilu/4272252 to your computer and use it in GitHub Desktop.
modular integers in Perl6
class Modular does Real {
our $.Modulus;
has ($.residue, $.modulus);
multi method new($residue, :$modulus where * > 1) { self.new: :residue($residue % $modulus), :$modulus }
method Bridge { $.residue % $.modulus }
multi method gist { "{self.Bridge} 「mod $.modulus" }
method succ { self.Bridge.succ % $.modulus }
multi method Inverse {
return Mu unless $.residue gcd $.modulus == 1;
my ($c, $d, $uc, $vc, $ud, $vd) = ($.residue, $.modulus, 1, 0, 0, 1);
my $q;
while $c != 0 {
($q, $c, $d) = ($d div $c, $d % $c, $c);
($uc, $vc, $ud, $vd) = ($ud - $q*$uc, $vd - $q*$vc, $uc, $vc);
}
return self.new: $ud < 0 ?? $ud + $.modulus !! $ud, :$.modulus;
}
}
sub mod($residue, $modulus = $Modular::Modulus) is export returns Modular { Modular.new: :$residue, :$modulus }
multi prefix:<->(Modular $a) is export returns Modular { Modular.new: -$a.Bridge, :modulus($a.modulus) }
multi infix:<->(Modular $a, Modular $b where $a.modulus ~~ $b.modulus) is export returns Modular {
Modular.new: $a.Bridge - $b.Bridge, :modulus($a.modulus)
}
proto infix:<+>($, $) is export returns Modular {*}
multi infix:<+>(Modular $a, Int $b) { Modular.new: $b + $a.Bridge, :modulus($a.modulus) }
multi infix:<+>(Int $a, Modular $b) { Modular.new: $a + $b.Bridge, :modulus($b.modulus) }
multi infix:<+>(Modular $a, Modular $b where $a.modulus ~~ $b.modulus) {
Modular.new: $a.Bridge + $b.Bridge, :modulus($a.modulus)
}
proto infix:<*>($, $) is export returns Modular {*}
multi infix:<*>(Int $a, Modular $b) { Modular.new: $a * $b.Bridge, :modulus($b.modulus) }
multi infix:<*>(Modular $a, Int $b) { Modular.new: $b * $a.Bridge, :modulus($a.modulus) }
multi infix:<*>(Modular $a, Modular $b where $a.modulus ~~ $b.modulus) {
Modular.new: $a.Bridge * $b.Bridge, :modulus($a.modulus)
}
proto infix:<div>($, $) is export returns Modular {*}
multi infix:<div>($a, Modular $b where $a.modulus ~~ $b.modulus) { $a * $b.Inverse }
proto infix:</>($, $) is export returns Modular {*}
multi infix:<div>(Modular $a, Modular $b where $a.modulus ~~ $b.modulus) { $a div $b }
proto infix:<**>($, $) is export returns Modular {*}
multi infix:<**>(Modular $a, Int $e) {
Modular.new: $a.Bridge.expmod($e, $a.modulus), :modulus($a.modulus)
}
# vim: ft=perl6
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment