Rosetta Code

Pell's equation: Difference between revisions

Page Discussion

Pell's equation (view source)

Revision as of 19:27, 1 May 2024

3,226 bytes added ,  17 days ago
→‎{{header|langur}}
(Added solution for Pascal.)
(9 intermediate revisions by 4 users not shown)
Line 19:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">F solvePell(n)
V x = Int(sqrt(n))
V (y, z, r) = (x, 1, x << 1)
Line 40:
L(n) [61, 109, 181, 277]
V (x, y) = solvePell(n)
print(‘x^2 - #3 * y^2 = 1 for x = #27 and y = #25’.format(n, x, y))</langsyntaxhighlight>
 
{{out}}
Line 52:
=={{header|Ada}}==
{{Trans|C}}{{works with|Ada 2022}}
<langsyntaxhighlight Adalang="ada">with Ada.Text_Io;
with Ada.Numerics.Elementary_Functions;
with Ada.Numerics.Big_Numbers.Big_Integers;
Line 116:
Test (181);
Test (277);
end Pells_Equation;</langsyntaxhighlight>
{{out}}
<pre>
Line 128:
{{Trans|Sidef}} Also tests for a trival solution only (if n is a perfect square only 1, 0 is solution).
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
<langsyntaxhighlight lang="algol68">BEGIN
# find solutions to Pell's eqauation: x^2 - ny^2 = 1 for integer x, y, n #
MODE BIGINT = LONG LONG INT;
Line 166:
print( ("x^2 - ", whole( n, -3 ), " * y^2 = 1 for x = ", whole( v1 OF r, -21), " and y = ", whole( v2 OF r, -21 ), newline ) )
OD
END</langsyntaxhighlight>
{{out}}
<pre>
Line 178:
{{trans|Python}}
 
<langsyntaxhighlight lang="rebol">solvePell: function [n][
x: to :integer sqrt n
[y, z, r]: @[x, 1, shl x 1]
Line 200:
[x, y]: solvePell n
print ["x² -" n "* y² = 1 for (x,y) =" x "," y]
]</langsyntaxhighlight>
 
{{out}}
Line 213:
{{trans|ALGOL 68}}
For n = 277, the x value is not correct because 64-bits is not enough to represent the value.
<langsyntaxhighlight lang="c">#include <math.h>
#include <stdbool.h>
#include <stdint.h>
Line 274:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>x^2 - 61 * y^2 = 1 for x = 1766319049 and y = 226153980
Line 284:
{{trans|C}}
As with the C solution, the output for n = 277 is not correct because 64-bits is not enough to represent the value.
<langsyntaxhighlight lang="cpp">#include <iomanip>
#include <iostream>
#include <tuple>
Line 333:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>x^2 - 61 * y^2 = 1 for x = 1766319049 and y = 226153980
Line 342:
=={{header|C sharp|C#}}==
{{trans|Sidef}}
<langsyntaxhighlight lang="csharp">using System;
using System.Numerics;
 
Line 372:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>x^2 - 61 * y^2 = 1 for x = 1,766,319,049 and y = 226,153,980
Line 381:
=={{header|D}}==
{{trans|C#}}
<langsyntaxhighlight lang="d">import std.bigint;
import std.math;
import std.stdio;
Line 421:
writefln("x^2 - %3d * y^2 = 1 for x = %27d and y = %25d", n, x, y);
}
}</langsyntaxhighlight>
{{out}}
<pre>x^2 - 61 * y^2 = 1 for x = 1766319049 and y = 226153980
Line 431:
{{libheader| Velthuis.BigIntegers}}
{{Trans|Go}}
<syntaxhighlight lang="delphi">
<lang Delphi>
program Pells_equation;
 
Line 501:
 
{$IFNDEF UNIX} readln; {$ENDIF}
end.</langsyntaxhighlight>
 
=={{header|Factor}}==
{{trans|Sidef}}
<langsyntaxhighlight lang="factor">USING: formatting kernel locals math math.functions sequences ;
 
:: solve-pell ( n -- a b )
Line 536:
dup solve-pell
"x^2 - %3d*y^2 = 1 for x = %-21d and y = %d\n" printf
] each</langsyntaxhighlight>
{{out}}
<pre>
Line 548:
{{trans|Visual Basic .NET}}
'''for n = 277 the result is wrong, I do not know if you can represent such large numbers in FreeBasic!'''
<langsyntaxhighlight lang="freebasic">
Sub Fun(Byref a As LongInt, Byref b As LongInt, c As Integer)
Dim As LongInt t
Line 573:
Print Using "x^2 - ### * y^2 = 1 for x = ##################### and y = #####################"; n(i); x; y
Next i
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 585:
=={{header|Go}}==
{{trans|Sidef}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 646:
fmt.Printf("x^2 - %3d*y^2 = 1 for x = %-21s and y = %s\n", n, x, y)
}
}</langsyntaxhighlight>
 
{{out}}
Line 658:
=={{header|Haskell}}==
{{trans|Julia}}
<langsyntaxhighlight lang="haskell">pell :: Integer -> (Integer, Integer)
pell n = go (x, 1, x * 2, 1, 0, 0, 1)
where
Line 672:
in if a' * a' - n * b' * b' == 1
then (a', b')
else go (y', z', r', e1', e2', f1', f2')</langsyntaxhighlight>
 
<pre>λ> mapM_ print $ pell <$> [61,109,181,277]
Line 682:
=={{header|J}}==
 
<langsyntaxhighlight Jlang="j">NB. sqrt representation for continued fraction
sqrt_cf =: 3 : 0
rep=. '' [ 'm d'=. 0 1 [ a =. a0=. <. %: y
Line 698:
end.
)
</syntaxhighlight>
</lang>
 
Check that task is actually solved
<langsyntaxhighlight Jlang="j">verify =: 3 : 0
assert. 1 = (*: xy) +/ . * 1 _61 [ echo 61 ; xy =. pell 61
assert. 1 = (*: xy) +/ . * 1 _109 [ echo 109 ; xy =. pell 109
Line 707:
assert. 1 = (*: xy) +/ . * 1 _277 [ echo 277 ; xy =. pell 277
)
</syntaxhighlight>
</lang>
{{out}}
<pre> verify ''
Line 725:
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">
import java.math.BigInteger;
import java.text.NumberFormat;
Line 811:
 
}
</syntaxhighlight>
</lang>
 
{{out}}
Line 841:
 
'''Preliminaries'''
<langsyntaxhighlight lang="jq"># If $j is 0, then an error condition is raised;
# otherwise, assuming infinite-precision integer arithmetic,
# if the input and $j are integers, then the result will be an integer.
Line 870:
then irt
else "isqrt requires a non-negative integer for accuracy" | error
end ;</langsyntaxhighlight>
'''The Task'''
<langsyntaxhighlight lang="jq">def solvePell:
. as $n
| ($n|isqrt) as $x
Line 900:
(61, 109, 181, 277)
| solvePell as $res
| "x² - \(.)y² = 1 for x = \($res[0]) and y = \($res[1])"</langsyntaxhighlight>
{{out}}
<pre>
Line 911:
=={{header|Julia}}==
{{trans|C#}}
<langsyntaxhighlight lang="julia">function pell(n)
x = BigInt(floor(sqrt(n)))
y, z, r = x, BigInt(1), x << 1
Line 933:
println("x\u00b2 - $target", "y\u00b2 = 1 for x = $x and y = $y")
end
</langsyntaxhighlight>{{out}}
<pre>
x² - 61y² = 1 for x = 1766319049 and y = 226153980
Line 943:
=={{header|Kotlin}}==
{{trans|C#}}
<langsyntaxhighlight lang="scala">import java.math.BigInteger
import kotlin.math.sqrt
 
Line 1,012:
println("x^2 - %3d * y^2 = 1 for x = %,27d and y = %,25d".format(it, x.value, y.value))
}
}</langsyntaxhighlight>
{{out}}
<pre>x^2 - 61 * y^2 = 1 for x = 1,766,319,049 and y = 226,153,980
Line 1,018:
x^2 - 181 * y^2 = 1 for x = 2,469,645,423,824,185,801 and y = 183,567,298,683,461,940
x^2 - 277 * y^2 = 1 for x = 159,150,073,798,980,475,849 and y = 9,562,401,173,878,027,020</pre>
 
=={{header|Lambdatalk}}==
Computing big numbers requires the lib_BN library.
<syntaxhighlight lang="Scheme">
{def pell
{lambda {:n}
{let { {:n :n}
{:x {BN.intPart {BN.sqrt :n}}} // x=int(sqrt(n))
} {pell.r :n :x :x 1 {* 2 :x} 1 0 0 1}
}}}
-> pell
 
{def pell.r
{lambda {:n :x :y :z :r :e1 :e2 :f1 :f2}
{let { {:n :n} {:x :x} {:z :z} {:r :r} // no closure ->
{:e1 :e1} {:e2 :e2} {:f1 :f1} {:f2 :f2} // must reassign :(
{:y {BN.- {BN.* :r :z} :y}} // y=rz-y
} {let { {:n :n} {:x :x} {:y :y} {:r :r}
{:e1 :e1} {:e2 :e2} {:f1 :f1} {:f2 :f2}
{:z {BN.intPart
{BN./ {BN.- :n {BN.* :y :y}} :z}}} // z=(n-y*y)//z
} {let { {:n :n} {:x :x} {:y :y} {:z :z}
{:e1 :e1} {:e2 :e2} {:f1 :f1} {:f2 :f2}
{:r {BN.intPart {BN./ {BN.+ :x :y} :z}}} // r= (x+y)//z
} {let { {:n :n} {:x :x} {:y :y} {:z :z} {:r :r}
{:e1 :e2} // e1=e2
{:e2 {BN.+ {BN.* :r :e2} :e1}} // e2=r*e2+e1
{:f1 :f2} // f1=f2
{:f2 {BN.+ {BN.* :r :f2} :f1}} // f2=r*f2+f1
} {let { {:n :n} {:x :x} {:y :y} {:z :z} {:r :r}
{:e1 :e1} {:e2 :e2} {:f1 :f1} {:f2 :f2}
{:a {BN.+ :e2 {BN.* :x :f2}}} // a=e2+x*f2
{:b :f2} // b=f2
} {if {= {BN.compare {BN.- {BN.* :a :a}
{BN.* :n {BN.* :b :b}}}
1}
0} // a*a-n*b*b == 1
then {div}x{sup 2} - n*y{sup 2} = 1 for n=:n, x=:a, y=:b
else {pell.r :n :x :y :z :r :e1 :e2 :f1 :f2} // do it again
}}}}}}}}
-> pell.r
{S.map pell 61 109 181 277}
->
x^2 - n*y^2 = 1 for n=61, x=1766319049, y=226153980
x^2 - n*y^2 = 1 for n=109, x=158070671986249, y=15140424455100
x^2 - n*y^2 = 1 for n=181, x=2469645423824185801, y=183567298683461940
x^2 - n*y^2 = 1 for n=277, x=159150073798980475849, y=9562401173878027020
</syntaxhighlight>
 
=={{header|langur}}==
{{trans|D}}
<langsyntaxhighlight lang="langur">val .fun = ffn(.a, .b, .c) { [.b, .b x* .c + .a] }▼
{{works with|langur|0.10}}
Prior to 0.10, multi-variable declaration/assignment would use parentheses around variable names and values.
 
▲<lang langur>val .fun = f [.b, .b x .c + .a]
 
val .solvePell = ffn(.n) {
val .x = truncatetrunc .n ^/ 2
var .y, .z, .r = .x, 1, .x x* 2
var .e1, .e2, .f1, .f2 = 1, 0, 0, 1
 
for {
.y = .r x* .z - .y
.z = (.n - .y x* .y) \ .z
.r = (.x + .y) \ .z
.e1, .e2 = .fun(.e1, .e2, .r)
.f1, .f2 = .fun(.f1, .f2, .r)
val .b, .a = .fun(.e2, .f2, .x)
if .a^2 - .n x* .b^2 == 1: return [.a, .b]
}
}
 
val .C = ffn(.x) {
# format number string with commas
var .neg, .s = ZLS"", toStringstring .x
if .s[1] == '-' {
.neg, .s = "-", rest .s
Line 1,053 ⟶ 1,099:
for .n in [61, 109, 181, 277, 8941] {
val .x, .y = .solvePell(.n)
writeln $"x² - \.n;y² = 1 for:\n\tx = \.x:.fn C;\n\ty = \.y:.fn C;\n"
}
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,080 ⟶ 1,126:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">FindInstance[x^2 - 61 y^2 == 1, {x, y}, PositiveIntegers]
FindInstance[x^2 - 109 y^2 == 1, {x, y}, PositiveIntegers]
FindInstance[x^2 - 181 y^2 == 1, {x, y}, PositiveIntegers]
FindInstance[x^2 - 277 y^2 == 1, {x, y}, PositiveIntegers]</langsyntaxhighlight>
{{out}}
<pre>{{x -> 1766319049, y -> 226153980}}
Line 1,093 ⟶ 1,139:
{{trans|Python}}
{{libheader|bignum}}
<langsyntaxhighlight Nimlang="nim">import math, strformat
import bignum
 
Line 1,116 ⟶ 1,162:
for n in [61, 109, 181, 277]:
let (x, y) = solvePell(n)
echo &"x² - {n:3} * y² = 1 for (x, y) = ({x:>21}, {y:>19})"</langsyntaxhighlight>
 
{{out}}
Line 1,129 ⟶ 1,175:
 
Pascal has no built-in support for arbitrarily large integers. The program below requires integers larger than 64 bits, and therefore uses an external library. The code could easily be adapted to solve the negative Pell equation x^2 - n*y^2 = -1, or show that no solution exists.
<langsyntaxhighlight lang="pascal">
program Pell_console;
uses SysUtils,
Line 1,201 ⟶ 1,247:
ShowPellSolution( 277);
end.
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,211 ⟶ 1,257:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">sub solve_pell {
my ($n) = @_;
 
Line 1,245 ⟶ 1,291:
my ($x, $y) = solve_pell($n);
printf("x^2 - %3d*y^2 = 1 for x = %-21s and y = %s\n", $n, $x, $y);
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,259 ⟶ 1,305:
{{libheader|Phix/mpfr}}
This now ignores the nonsquare part of the task spec, returning {1,0}.
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 1,322 ⟶ 1,368:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"x^2 - %3d*y^2 = 1 for x = %27s and y = %25s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">xs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ys</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,342 ⟶ 1,388:
=={{header|Prolog}}==
pell(A, X, Y) finds all solutions X, Y s.t. X^2 - A*Y^2 = 1. Therefore the once() predicate can be used to only select the first one.
<syntaxhighlight lang="prolog">
<lang Prolog>
% Find the square root as a continued fraction
 
Line 1,391 ⟶ 1,437:
X2 is X0*X1 + N*Y0*Y1,
Y2 is X0*Y1 + Y0*X1.
</syntaxhighlight>
</lang>
{{Out}}
<pre>
Line 1,421 ⟶ 1,467:
=={{header|Python}}==
{{trans|D}}
<langsyntaxhighlight lang="python">import math
 
def solvePell(n):
Line 1,442 ⟶ 1,488:
for n in [61, 109, 181, 277]:
x, y = solvePell(n)
print("x^2 - %3d * y^2 = 1 for x = %27d and y = %25d" % (n, x, y))</langsyntaxhighlight>
{{out}}
<pre>x^2 - 61 * y^2 = 1 for x = 1766319049 and y = 226153980
Line 1,454 ⟶ 1,500:
{{trans|Perl}}
 
<syntaxhighlight lang="raku" perl6line>use Lingua::EN::Numbers;
 
sub pell (Int $n) {
Line 1,486 ⟶ 1,532:
my ($x, $y) = pell($n);
printf "x² - %sy² = 1 for:\n\tx = %s\n\ty = %s\n\n", $n, |($x, $y)».&comma;
}</langsyntaxhighlight>
{{out}}
<pre>x² - 61y² = 1 for:
Line 1,510 ⟶ 1,556:
=={{header|REXX}}==
A little extra code was added to align and commatize the gihugeic numbers for readability.
<langsyntaxhighlight lang="rexx">/*REXX program to solve Pell's equation for the smallest solution of positive integers. */
numeric digits 2200 /*ensure enough decimal digs for answer*/
parse arg $ /*obtain optional arguments from the CL*/
Line 1,539 ⟶ 1,585:
parse value f2 r*f2 + f1 with f1 f2
end /*until*/
return e2 + x * f2 f2</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
Line 1,550 ⟶ 1,596:
=={{header|Ruby}}==
{{trans|Sidef}}
<langsyntaxhighlight lang="ruby">def solve_pell(n)
x = Integer.sqrt(n)
y = x
Line 1,570 ⟶ 1,616:
 
[61, 109, 181, 277].each {|n| puts "x*x - %3s*y*y = 1 for x = %-21s and y = %s" % [n, *solve_pell(n)]}
</syntaxhighlight>
</lang>
{{Out}}
<pre>
Line 1,580 ⟶ 1,626:
</pre>
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">
use num_bigint::{ToBigInt, BigInt};
use num_traits::{Zero, One};
Line 1,640 ⟶ 1,686:
println!("x^2 - {} * y^2 = 1 for x = {} and y = {}", n, r.v1, r.v2);
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,650 ⟶ 1,696:
 
=={{header|Scala}}==
<langsyntaxhighlight lang="scala">def pellFermat(n: Int): (BigInt,BigInt) = {
import scala.math.{sqrt, floor}
 
Line 1,683 ⟶ 1,729:
println("For Pell's Equation, x\u00b2 - ny\u00b2 = 1\n")
(nums zip solutions).foreach{ case (n, (x,y)) => println(s"n = $n, x = $x, y = $y")}
}</langsyntaxhighlight>
{{out}}
<pre>For Pell's Equation, x² - ny² = 1
Line 1,693 ⟶ 1,739:
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func solve_pell(n) {
 
var x = n.isqrt
Line 1,724 ⟶ 1,770:
var (x, y) = solve_pell(n)
printf("x^2 - %3d*y^2 = 1 for x = %-21s and y = %s\n", n, x, y)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,738 ⟶ 1,784:
{{libheader|AttaSwift's BigInt}}
 
<langsyntaxhighlight lang="swift">func solvePell<T: BinaryInteger>(n: T, _ a: inout T, _ b: inout T) {
func swap(_ a: inout T, _ b: inout T, mul by: T) {
(a, b) = (b, b * by + a)
Line 1,777 ⟶ 1,823:
 
print("x\u{00b2} - \(n)y\u{00b2} = 1 for x = \(x) and y = \(y)")
}</langsyntaxhighlight>
 
{{out}}
Line 1,788 ⟶ 1,834:
=={{header|Visual Basic .NET}}==
{{trans|Sidef}}
<langsyntaxhighlight lang="vbnet">Imports System.Numerics
 
Module Module1
Line 1,812 ⟶ 1,858:
Next
End Sub
End Module</langsyntaxhighlight>
{{out}}
<pre>x^2 - 61 * y^2 = 1 for x = 1,766,319,049 and y = 226,153,980
Line 1,823 ⟶ 1,869:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./big" for BigInt
import "./fmt" for Fmt
 
var solvePell = Fn.new { |n|
Line 1,855 ⟶ 1,901:
var res = solvePell.call(n)
Fmt.print("x² - $3dy² = 1 for x = $-21i and y = $i", n, res[0], res[1])
}</langsyntaxhighlight>
 
{{out}}
Line 1,868 ⟶ 1,914:
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library
{{trans|Raku}}
<langsyntaxhighlight lang="zkl">var [const] BI=Import("zklBigNum"); // libGMP
 
fcn solve_pell(n){
Line 1,884 ⟶ 1,930:
if (A*A - B*B*n == 1) return(A,B);
}
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">foreach n in (T(61, 109, 181, 277)){
x,y:=solve_pell(n);
println("x^2 - %3d*y^2 = 1 for x = %-21d and y = %d".fmt(n,x,y));
}</langsyntaxhighlight>
 
{{out}}
Langurmonkey
885

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/287889...364148"