Anonymous user
Formal power series: Difference between revisions
→{{header|Maxima}}
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: Fix comment: Perl 6 --> Raku) |
|||
Line 1,768:
taylor(fcos(x)^2 + fsin(x)^2, x, 0, 20);
/ * 1 + ... * /</lang>
=={{header|Nim}}==
===Using C algorithm===
The program is based on C algorithm but uses rationals instead of floats. There are many other differences in order to use Nim facilities (for instance, function and operator overloading) and some parts were borrowed from Kotlin version.
<lang Nim>import rationals, tables
type
Fraction = Rational[int]
FpsKind = enum fpsConst, fpsAdd, fpsSub, fpsMul, fpsDiv, fpsDeriv, fpsInteg
Fps = ref object
kind: FpsKind
s1, s2: Fps
a0: Fraction
cache: Table[Natural, Fraction]
const
Zero: Fraction = 0 // 1
One: Fraction = 1 // 1
DispTerm = 12
XVar = "x"
Super: array['0'..'9', string] = ["⁰", "¹", "²", "³", "⁴", "⁵", "⁶", "⁷", "⁸", "⁹"]
#---------------------------------------------------------------------------------------------------
proc `$`(fract: Fraction): string =
## Return the representation of a fraction without the denominator if it is equal to 1.
if fract.den == 1: $fract.num else: rationals.`$`(fract)
#---------------------------------------------------------------------------------------------------
proc exponent(n: Natural): string =
## Return the representation of an exponent using unicode superscript.
if n == 1: return ""
for d in $n: result.add(Super[d])
####################################################################################################
# FPS.
func newFps*(val = 0): Fps =
## Build a FPS of kind fpsConst using the given integer value.
Fps(kind: fpsConst, a0: val // 1)
#---------------------------------------------------------------------------------------------------
func newFps*(val: Fraction): Fps =
## Build a FPS of kind fpsConst using the given fraction.
Fps(kind: fpsConst, a0: val)
#---------------------------------------------------------------------------------------------------
func newFps*(op: FpsKind; x: Fps; y: Fps = nil): Fps =
## Build a FPS for a unary or binary operation.
Fps(kind: op, s1: x, s2: y, a0: Zero)
#---------------------------------------------------------------------------------------------------
func redefine*(fps: Fps; other: Fps) =
## Redefine a FPS, modifying its kind ans its operands.
fps.kind = other.kind
fps.s1 = other.s1
fps.s2 = other.s2
#---------------------------------------------------------------------------------------------------
## Operations on FPS.
func `+`*(x, y: Fps): Fps = newFps(fpsAdd, x, y)
func `-`*(x, y: Fps): Fps = newFps(fpsSub, x, y)
func `*`*(x, y: Fps): Fps = newFps(fpsMul, x, y)
func `/`*(x, y: Fps): Fps = newFps(fpsDiv, x, y)
func derivative*(x: Fps): Fps = newFps(fpsDeriv, x)
func integral*(x: Fps): Fps = newFps(fpsInteg, x)
#---------------------------------------------------------------------------------------------------
func `[]`*(fps: Fps; n: Natural): Fraction =
## Return the nth term of the FPS.
if n in fps.cache: return fps.cache[n]
case fps.kind
of fpsConst:
result = if n > 0: Zero else: fps.a0
of fpsAdd:
result = fps.s1[n] + fps.s2[n]
of fpsSub:
result = fps.s1[n] - fps.s2[n]
of fpsMul:
result = Zero
for i in 0..n: result += fps.s1[i] * fps.s2[n - i]
of fpsDiv:
let d = fps.s2[0]
if d == Zero: raise newException(DivByZeroDefect, "Division by null fraction")
result = fps.s1[n]
for i in 1..n: result -= fps.s2[i] * fps[n - i] / d
of fpsDeriv:
result = fps.s1[n + 1] * (n + 1)
of fpsInteg:
result = if n > 0: fps.s1[n - 1] / n else: fps.a0
fps.cache[n] = result
#---------------------------------------------------------------------------------------------------
proc `$`*(fps: Fps): string =
## Return the representation of a FPS.
var c = fps[0]
if c != Zero: result &= $c
for i in 1..<DispTerm:
c = fps[i]
if c != Zero:
if c > Zero:
if result.len > 0: result &= " + "
else:
result &= " - "
c = -c
result &= (if c == One: XVar else: $c & XVar) & exponent(i)
if result.len == 0: result &= '0'
result &= " + ..."
#———————————————————————————————————————————————————————————————————————————————————————————————————
# Build cos, sin and tan.
var cos = newFps()
let sin = cos.integral()
let tan = sin / cos
cos.redefine(newFps(1) - sin.integral())
echo "sin(x) = ", sin
echo "cos(x) = ", cos
echo "tan(x) = ", tan
# Check that derivative of sin is cos.
echo "derivative of sin(x) = ", sin.derivative()
# Build exp using recursion.
let exp = newFps()
exp.redefine(newFps(1) + exp.integral())
echo "exp(x) = ", exp</lang>
{{out}}
<pre>sin(x) = x - 1/6x³ + 1/120x⁵ - 1/5040x⁷ + 1/362880x⁹ - 1/39916800x¹¹ + ...
cos(x) = 1 - 1/2x² + 1/24x⁴ - 1/720x⁶ + 1/40320x⁸ - 1/3628800x¹⁰ + ...
tan(x) = x + 1/3x³ + 2/15x⁵ + 17/315x⁷ + 62/2835x⁹ + 1382/155925x¹¹ + ...
derivative of sin(x) = 1 - 1/2x² + 1/24x⁴ - 1/720x⁶ + 1/40320x⁸ - 1/3628800x¹⁰ + ...
exp(x) = 1 + x + 1/2x² + 1/6x³ + 1/24x⁴ + 1/120x⁵ + 1/720x⁶ + 1/5040x⁷ + 1/40320x⁸ + 1/362880x⁹ + 1/3628800x¹⁰ + 1/39916800x¹¹ + ...</pre>
===Using closure functions===
This version is largely inspired from Kotlin version even if the way to implement the algorithm is pretty different.
<lang Nim>import rationals, sequtils
type
Fraction = Rational[int]
# Function to compute coefficients.
CoeffFunc = proc(n: int): Fraction
# Formal power series.
Fps = ref object
cache: seq[Fraction] # Cache to store values.
coeffs: CoeffFunc # Function to compute coefficients.
const
Zero: Fraction = 0 // 1
One: Fraction = 1 // 1
XVar = "x"
DispTerm = 12
Super: array['0'..'9', string] = ["⁰", "¹", "²", "³", "⁴", "⁵", "⁶", "⁷", "⁸", "⁹"]
#---------------------------------------------------------------------------------------------------
proc `$`(fract: Fraction): string =
## Return the representation of a fraction without the denominator if it is equal to 1.
if fract.den == 1: $fract.num else: rationals.`$`(fract)
#---------------------------------------------------------------------------------------------------
proc exponent(n: Natural): string =
## Return the representation of an exponent using unicode superscript.
if n == 1: return ""
for d in $n: result.add(Super[d])
####################################################################################################
# FPS.
func newFps*(coeffs: CoeffFunc): Fps =
## Create a FPS using the given "coeffs" function.
Fps(coeffs: coeffs)
#---------------------------------------------------------------------------------------------------
func newFps*(coeffs: seq[Fraction]): Fps =
## Create a FPS using a list of fractions to initialize coefficients.
Fps(coeffs: proc(n: int): Fraction = (if n in 0..coeffs.high: coeffs[n] else: Zero))
#---------------------------------------------------------------------------------------------------
func newFps*(coeffs: seq[int]): Fps =
## Create a FPS using a list of integer values to initialize coefficients.
Fps(coeffs: proc(n: int): Fraction = (if n in 0..coeffs.high: coeffs[n] // 1 else: Zero))
#---------------------------------------------------------------------------------------------------
func copyFrom(dest, src: Fps) {.inline.} =
## Copy a FPS into another.
dest[] = src[]
#---------------------------------------------------------------------------------------------------
proc `[]`*(fps: Fps; n: int): Fraction =
## Return the element of degree "n" from a FPS.
if n < 0: return Zero
for i in fps.cache.len..n:
fps.cache.add(fps.coeffs(i))
result = fps.cache[n]
#---------------------------------------------------------------------------------------------------
proc inverseCoeff*(fps: FPS; n: int): Fraction =
## Return the inverse coefficient of coefficient of degree "n".
var res = repeat(Zero, n + 1)
res[0] = fps[0].reciprocal
for i in 1..n:
for j in 0..<i: res[i] += fps[i - j] * res[j]
res[i] *= -res[0]
result = res[n]
#---------------------------------------------------------------------------------------------------
proc `+`*(a, b: Fps): Fps =
## Build the FPS sum of two FPS.
Fps(coeffs: proc(n: int): Fraction = a[n] + b[n])
#---------------------------------------------------------------------------------------------------
proc `-`*(a, b: Fps): Fps =
## Build the FPS difference of two FPS.
Fps(coeffs: proc(n: int): Fraction = a[n] - b[n])
#---------------------------------------------------------------------------------------------------
proc `*`*(a, b: Fps): Fps =
## Build the FPS product of two FPS.
Fps(coeffs: proc(n: int): Fraction =
result = Zero
for i in 0..n: result += a[i] * b[n - i])
#---------------------------------------------------------------------------------------------------
proc `/`*(a, b: Fps): Fps =
## Build the FPS quotient of two FPS.
Fps(coeffs: proc(n: int): Fraction =
result = Zero
for i in 0..n: result += a[i] * b.inverseCoeff(n - i))
#---------------------------------------------------------------------------------------------------
proc derivative*(fps: Fps): Fps =
## Build the FPS derivative of a FPS.
Fps(coeffs: proc(n: int): Fraction = fps[n + 1] * (n + 1))
#---------------------------------------------------------------------------------------------------
proc integral*(fps: Fps): Fps =
## Build the FPS integral of a FPS.
Fps(coeffs: proc(n: int): Fraction = (if n == 0: Zero else: fps[n - 1] / n))
#---------------------------------------------------------------------------------------------------
proc `$`*(fps: Fps): string =
## Return the representation of a FPS.
var c = fps[0]
if c != Zero: result &= $c
for i in 1..<DispTerm:
c = fps[i]
if c != Zero:
if c > Zero:
if result.len > 0: result &= " + "
else:
result &= " - "
c = -c
result &= (if c == One: XVar else: $c & XVar) & exponent(i)
if result.len == 0: result &= '0'
result &= " + ..."
#———————————————————————————————————————————————————————————————————————————————————————————————————
# Build cos, sin and tan.
var cos = Fps()
let sin = cos.integral()
cos.copyFrom(newFps(@[1]) - sin.integral())
let tan = sin / cos
echo "sin(x) = ", sin
echo "cos(x) = ", cos
echo "tan(x) = ", tan
# Check that derivative of sin is cos.
echo "derivative of sin(x) = ", sin.derivative()
# Build exp using recursion.
let exp = Fps()
exp.copyFrom(newFps(@[1]) + exp.integral())
echo "exp(x) = ", exp</lang>
{{out}}
Same as with the other version.
=={{header|PARI/GP}}==
| |||