Modular arithmetic: Difference between revisions
→{{header|jq}}: ring::f
(→{{header|jq}}: ring::f) |
|||
Line 745:
'''Works with gojq, the Go implementation of jq'''
This entry focuses on the requirement that the function, f, "should behave the same way with normal and modular integers."
To illustrate that the function `ring::f` defined here does satisfy this requirement, we will evaluate it at both the integer 1 and the
element «10 % 13» of Z/13Z.
To keep the distinctions between functions defined on different
types clear, this entry uses jq's support for name
spaces. Specifically, we will use the prefix "modint::" for the
modular arithmetic functions, and "ring::" for the generic ring
functions.
<lang jq>▼
Since jq supports neither redefining any of the symbolic operators
# In this module, "ModularArithmetic" objects are represented by JSON objects of the form: {value, mod}.▼
(such as "+") nor dynamic dispatch, ring functions (such as
# The function modint::assert/0 checks the input is of this form with integer values.▼
`ring::add`) must be written with the specific rings that are to be
supported in mind.
<lang jq>def assert($e; $msg): if $e then . else "assertion violation @ \($msg)" | error end;
def is_integer: type=="number" and floor == .;
# To take advantage of gojq's arbitrary-precision integer arithmetic:
def assert:▼
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
'''Modular Arithmetic'''
▲<lang jq>#
▲# The function modint::assert/0 checks the input is of this form with integer values.
def is_modint: type=="object" and has("value") and has("mod");
▲def modint::assert:
assert(type=="object"; "object expected")
| assert(has("value"); "object should have a value")
Line 774 ⟶ 782:
| assert(.mod | is_integer; "mod should be an integer");
assert($value|is_integer; "value should be an integer")
| assert($mod|is_integer; "mod should be an integer")
| { value: ($value % $mod), mod: $mod};
def modint::add($
if ($B|type) == "object"
then assert($
| modint::make( $
else modint::make( $
end;
def modint::mul($
if ($B|type) == "object"
then assert($
| modint::make( $
else modint::make( $
end;
def modint::pow($
assert($pow | is_integer; "pow")
| reduce range(0; $pow) as $i ( modint::make(1; $
modint::mul( .; $
# pretty print
def modint::pp: "«\(.value) % \(.mod)»";</lang>
''' Ring Functions'''
<lang jq>def ring::add($A; $B):
if $A|is_modint then modint::add($A; $B)
elif $A|is_integer then $A + $B
else "ring::add" | error
end;
def
if $A|is_modint then modint::mul($A; $B)
add( add( pow($x; 100); $x); 1);▼
elif $A|is_integer then $A * $B
else "ring::mul" | error
end;
def ring::pow($A; $B):
if $A|is_modint then modint::pow($A; $B)
elif $A|is_integer then $A|power($B)
else "ring::pow" | error
end;
def ring::pp:
if is_modint then modint::pp
elif is_integer then .
else "ring::pp" | error
end;
def
▲ ring::add( ring::add( ring::pow($x; 100); $x); 1);</lang>
make(10;13)▼
'''Evaluating ring::f'''
| f(.) as $out▼
<lang jq>def main:
| "f(\(pp)) => \($out|pp)";</lang>▼
(ring::f(1) | "f(\(1)) => \(.)"),
▲ (modint::make(10;13)
▲ | ring::f(.) as $out
▲ | "f(\(ring::pp)) => \($out|ring::pp)");</lang>
{{out}}
<pre>
f(1) => 3
f(«10 % 13») => «1 % 13»
</pre>
| |||