Minkowski question-mark function: Difference between revisions
Content deleted Content added
Add C# implementation |
|||
(11 intermediate revisions by 4 users not shown) | |||
Line 128:
</pre>
=={{header|C#}}==
{{trans|Go}}
<syntaxhighlight lang="C#">
using System;
class Program
{
const int MAXITER = 151;
static double Minkowski(double x)
{
if (x > 1 || x < 0)
{
return Math.Floor(x) + Minkowski(x - Math.Floor(x));
}
ulong p = (ulong)x;
ulong q = 1;
ulong r = p + 1;
ulong s = 1;
double d = 1.0;
double y = (double)p;
while (true)
{
d = d / 2;
if (y + d == y)
{
break;
}
ulong m = p + r;
if (m < 0 || p < 0)
{
break;
}
ulong n = q + s;
if (n < 0)
{
break;
}
if (x < (double)m / (double)n)
{
r = m;
s = n;
}
else
{
y = y + d;
p = m;
q = n;
}
}
return y + d;
}
static double MinkowskiInv(double x)
{
if (x > 1 || x < 0)
{
return Math.Floor(x) + MinkowskiInv(x - Math.Floor(x));
}
if (x == 1 || x == 0)
{
return x;
}
uint[] contFrac = new uint[] { 0 };
uint curr = 0;
uint count = 1;
int i = 0;
while (true)
{
x *= 2;
if (curr == 0)
{
if (x < 1)
{
count++;
}
else
{
i++;
Array.Resize(ref contFrac, i + 1);
contFrac[i - 1] = count;
count = 1;
curr = 1;
x--;
}
}
else
{
if (x > 1)
{
count++;
x--;
}
else
{
i++;
Array.Resize(ref contFrac, i + 1);
contFrac[i - 1] = count;
count = 1;
curr = 0;
}
}
if (x == Math.Floor(x))
{
contFrac[i] = count;
break;
}
if (i == MAXITER)
{
break;
}
}
double ret = 1.0 / contFrac[i];
for (int j = i - 1; j >= 0; j--)
{
ret = contFrac[j] + 1.0 / ret;
}
return 1.0 / ret;
}
static void Main(string[] args)
{
Console.WriteLine("{0,19:0.0000000000000000} {1,19:0.0000000000000000}", Minkowski(0.5 * (1 + Math.Sqrt(5))), 5.0 / 3.0);
Console.WriteLine("{0,19:0.0000000000000000} {1,19:0.0000000000000000}", MinkowskiInv(-5.0 / 9.0), (Math.Sqrt(13) - 7) / 6);
Console.WriteLine("{0,19:0.0000000000000000} {1,19:0.0000000000000000}", Minkowski(MinkowskiInv(0.718281828)),
MinkowskiInv(Minkowski(0.1213141516171819)));
}
}
</syntaxhighlight>
{{out}}
<pre>
1.6666666666697000 1.6666666666666700
-0.5657414540893350 -0.5657414540893350
0.7182818280000090 0.1213141516171820
</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>
constexpr int32_t MAX_ITERATIONS = 151;
double minkowski(const double& x) {
if ( x < 0 || x > 1 ) {
return floor(x) + minkowski(x - floor(x));
}
int64_t p = (int64_t) x;
int64_t q = 1;
int64_t r = p + 1;
int64_t s = 1;
double d = 1.0;
double y = (double) p;
while ( true ) {
d /= 2;
if ( d == 0.0 ) {
break;
}
int64_t m = p + r;
if ( m < 0 || p < 0 ) {
break;
}
int64_t n = q + s;
if ( n < 0 ) {
break;
}
if ( x < (double) m / n ) {
r = m;
s = n;
} else {
y += d;
p = m;
q = n;
}
}
return y + d;
}
double minkowski_inverse(double x) {
if ( x < 0 || x > 1 ) {
return floor(x) + minkowski_inverse(x - floor(x));
}
if ( x == 0 || x == 1 ) {
return x;
}
std::vector<int32_t> continued_fraction(1, 0);
int32_t current = 0;
int32_t count = 1;
int32_t i = 0;
while ( true ) {
x *= 2;
if ( current == 0 ) {
if ( x < 1 ) {
count += 1;
} else {
continued_fraction.emplace_back(0);
continued_fraction[i] = count;
i += 1;
count = 1;
current = 1;
x -= 1;
}
} else {
if ( x > 1 ) {
count += 1;
x -= 1;
} else {
continued_fraction.emplace_back(0);
continued_fraction[i] = count;
i += 1;
count = 1;
current = 0;
}
}
if ( x == floor(x) ) {
continued_fraction[i] = count;
break;
}
if ( i == MAX_ITERATIONS ) {
break;
}
}
double reciprocal = 1.0 / continued_fraction[i];
for ( int32_t j = i - 1; j >= 0; --j ) {
reciprocal = continued_fraction[j] + 1.0 / reciprocal;
}
return 1.0 / reciprocal;
}
int main() {
std::cout << std::setw(20) << std::fixed << std::setprecision(16) << minkowski(0.5 * ( 1 + sqrt(5) ))
<< std::setw(20) << 5.0 / 3.0 << std::endl;
std::cout << std::setw(20) << minkowski_inverse(-5.0 / 9.0)
<< std::setw(20) << ( sqrt(13) - 7 ) / 6 << std::endl;
std::cout << std::setw(20) << minkowski(minkowski_inverse(0.718281828182818))
<< std::setw(20) << 0.718281828182818 << std::endl;
std::cout << std::setw(20) << minkowski_inverse(minkowski(0.1213141516271819))
<< std::setw(20) << 0.1213141516171819 << std::endl;
}
</syntaxhighlight>
{{ out }}
<pre>
1.6666666666696983 1.6666666666666667
-0.5657414540893351 -0.5657414540893352
0.7182818281828269 0.7182818281828180
0.1213141516171819 0.1213141516171819
</pre>
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
// Minkowski question-mark function. Nigel Galloway: July 14th., 2023
let fN g=let n=(int>>float)g in ((if g<0.0 then -1.0 else 1.0),abs n,abs (g-n))
let fI(n,_,(nl,nh))(g,_,(gl,gh))=let l,h=nl+gl,nh+gh in ((n+g)/2.0,(float l)/(float h),(l,h))
let fG n g=(max n g)-(min n g)
let fE(s,z,l)=Seq.unfold(fun(i,e)->let (n,g,_) as r=fI i e in Some((s*(z+n),s*(g+z)),if l<n then (i,r) else if l=n then (r,r) else (r,e)))((0.0,0.0,(0,1)),(1.0,1.0,(1,1)))
let fL(s,z,l)=Seq.unfold(fun(i,e)->let (n,g,_) as r=fI i e in Some((s*(z+n),s*(g+z)),if l<g then (i,r) else if l=g then (r,r) else (r,e)))((0.0,0.0,(0,1)),(1.0,1.0,(1,1)))
let f2M g=let _,(n,_)=fL(fN g)|>Seq.pairwise|>Seq.find(fun((n,_),(g,_))->(fG n g)<2.328306437e-11) in n
let m2F g=let _,(_,n)=fE(fN g)|>Seq.pairwise|>Seq.find(fun((_,n),(_,g))->(fG n g)<2.328306437e-11) in n
printfn $"?(φ) = 5/3 is %A{fG(f2M 1.61803398874989490253)(5.0/3.0)<2.328306437e-10}"
printfn $"?⁻¹(-5/9) = (√13-7)/6 is %A{fG(m2F(-5.0/9.0))((sqrt(13.0)-7.0)/6.0)<2.328306437e-10}"
let n=42.0/23.0 in printfn $"?⁻¹(?(n)) = n is %A{(fG(m2F(f2M n)) n)<2.328306437e-10}"
let n= -3.0/13.0 in printfn $"?(?⁻¹(n)) = n is %A{(fG(f2M(m2F n)) n)<2.328306437e-10}"
</syntaxhighlight>
{{out}}
<pre>
?(φ) = 5/3 is true
?⁻¹(-5/9) = (√13-7)/6 is true
?⁻¹(?(n)) = n is true
?(?⁻¹(n)) = n is true
</pre>
=={{header|Factor}}==
{{works with|Factor|0.99 2020-08-14}}
Line 516 ⟶ 805:
Using an exact fraction for 4.04145188432738056 and bumping the iteration count from 52 up to 200 changes that difference to 1.43622e_12.
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.List;
public final class MinkowskiQuestionMarkFunction {
public static void main(String[] aArgs) {
System.out.println(String.format("%20.16f%20.16f", minkowski(0.5 * ( 1 + Math.sqrt(5) )), 5.0 / 3.0));
System.out.println(String.format("%20.16f%20.16f", minkowskiInverse(-5.0 / 9.0), ( Math.sqrt(13) - 7 ) / 6 ));
System.out.println(String.format("%20.16f%20.16f", minkowski(minkowskiInverse(0.718281828)), 0.718281828));
System.out.println(String.format("%20.16f%20.16f",
minkowskiInverse(minkowski(0.1213141516271819)), 0.1213141516171819));
}
private static double minkowski(double aX) {
if ( aX < 0 || aX > 1 ) {
return Math.floor(aX) + minkowski(aX - Math.floor(aX));
}
long p = (long) aX;
long q = 1;
long r = p + 1;
long s = 1;
double d = 1.0;
double y = (double) p;
while ( true ) {
d /= 2;
if ( d == 0.0 ) {
break;
}
long m = p + r;
if ( m < 0 || p < 0 ) {
break;
}
long n = q + s;
if ( n < 0 ) {
break;
}
if ( aX < (double) m / n ) {
r = m;
s = n;
} else {
y += d;
p = m;
q = n;
}
}
return y + d;
}
private static double minkowskiInverse(double aX) {
if ( aX < 0 || aX > 1 ) {
return Math.floor(aX) + minkowskiInverse(aX - Math.floor(aX));
}
if ( aX == 0 || aX == 1 ) {
return aX;
}
List<Integer> continuedFraction = new ArrayList<Integer>();
continuedFraction.add(0);
int current = 0;
int count = 1;
int i = 0;
while ( true ) {
aX *= 2;
if ( current == 0 ) {
if ( aX < 1 ) {
count += 1;
} else {
continuedFraction.add(0);
continuedFraction.set(i, count);
i += 1;
count = 1;
current = 1;
aX -= 1;
}
} else {
if ( aX > 1 ) {
count += 1;
aX -= 1;
} else {
continuedFraction.add(0);
continuedFraction.set(i, count);
i += 1;
count = 1;
current = 0;
}
}
if ( aX == Math.floor(aX) ) {
continuedFraction.set(i, count);
break;
}
if ( i == MAX_ITERATIONS ) {
break;
}
}
double reciprocal = 1.0 / continuedFraction.get(i);
for ( int j = i - 1; j >= 0; j-- ) {
reciprocal = continuedFraction.get(j) + 1.0 / reciprocal;
}
return 1.0 / reciprocal;
}
private static final int MAX_ITERATIONS = 150;
}
</syntaxhighlight>
{{ out }}
<pre>
1.6666666666696983 1.6666666666666667
-0.5657414540893351 -0.5657414540893352
0.7182818280000092 0.7182818280000000
0.1213141516271825 0.1213141516171819
</pre>
=={{header|Julia}}==
Line 532 ⟶ 949:
y, bits = fldmod(x, 1)
lo, hi = [0, 1], [1, 1]
while (y + /(lo...))
bit, bits = fldmod(
bit > 0 ? (lo .+= hi) : (hi .+= lo)
end
y + /
end
x, y = 0.
for (a, b) ∈ [
(5/3, questionmark((1 + √5)/2)),
Line 549 ⟶ 966:
</syntaxhighlight>{{out}}
<pre>
-0.5657414540893352 ≈ -0.5657414540893351
0.
0.1213141516171819 ≈ 0.12131415161718095
</pre>
Line 1,069 ⟶ 1,486:
{{trans|FreeBASIC}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
var MAXITER = 151
|