Rosetta Code

Zeckendorf arithmetic: Difference between revisions

Page Discussion

Zeckendorf arithmetic (view source)

Revision as of 09:13, 7 May 2024

8,232 bytes added ,  13 days ago
m
→‎{{header|11l}}: Void
m (→‎{{header|Quackery}}: another typo)
 
(9 intermediate revisions by 5 users not shown)
Line 134:
.inc()
 
F inc() -> NVoid
.dVal = .dVal + 1
.a(0)
Line 972:
1000100
1000100</pre>
 
=={{header|Dart}}==
{{trans|Kotlin}}
<syntaxhighlight lang="Dart">
class Zeckendorf {
int dVal = 0;
int dLen = 0;
 
Zeckendorf(String x) {
var q = 1;
var i = x.length - 1;
dLen = i ~/ 2;
while (i >= 0) {
dVal += (x[i].codeUnitAt(0) - '0'.codeUnitAt(0)) * q;
q *= 2;
i--;
}
}
 
void a(int n) {
var i = n;
while (true) {
if (dLen < i) dLen = i;
var j = (dVal >> (i * 2)) & 3;
switch (j) {
case 0:
case 1:
return;
case 2:
if (((dVal >> ((i + 1) * 2)) & 1) != 1) return;
dVal += 1 << (i * 2 + 1);
return;
case 3:
dVal &= ~(3 << (i * 2));
b((i + 1) * 2);
break;
}
i++;
}
}
 
void b(int pos) {
if (pos == 0) {
this.increment();
return;
}
if (((dVal >> pos) & 1) == 0) {
dVal += 1 << pos;
a(pos ~/ 2);
if (pos > 1) a(pos ~/ 2 - 1);
} else {
dVal &= ~(1 << pos);
b(pos + 1);
b(pos - (pos > 1 ? 2 : 1));
}
}
 
void c(int pos) {
if (((dVal >> pos) & 1) == 1) {
dVal &= ~(1 << pos);
return;
}
c(pos + 1);
if (pos > 0)
b(pos - 1);
else
this.increment();
}
 
Zeckendorf increment() {
dVal += 1;
a(0);
return this;
}
 
void operator + (Zeckendorf other) {
for (var gn = 0; gn < (other.dLen + 1) * 2; gn++) {
if (((other.dVal >> gn) & 1) == 1) b(gn);
}
}
 
void operator - (Zeckendorf other) {
for (var gn = 0; gn < (other.dLen + 1) * 2; gn++) {
if (((other.dVal >> gn) & 1) == 1) c(gn);
}
while (dLen > 0 && (((dVal >> dLen * 2) & 3) == 0)) dLen--;
}
 
 
void operator * (Zeckendorf other) {
var na = other.copy();
var nb = other.copy();
Zeckendorf nt;
var nr = Zeckendorf("0");
for (var i = 0; i <= (dLen + 1) * 2; i++) {
if (((dVal >> i) & 1) > 0) nr + nb;
nt = nb.copy();
nb + na;
na = nt.copy();
}
dVal = nr.dVal;
dLen = nr.dLen;
}
 
int compareTo(Zeckendorf other) {
return dVal.compareTo(other.dVal);
}
 
@override
String toString() {
if (dVal == 0) return "0";
var sb = StringBuffer(dig1[(dVal >> (dLen * 2)) & 3]);
for (var i = dLen - 1; i >= 0; i--) {
sb.write(dig[(dVal >> (i * 2)) & 3]);
}
return sb.toString();
}
 
Zeckendorf copy() {
var z = Zeckendorf("0");
z.dVal = dVal;
z.dLen = dLen;
return z;
}
 
static final List<String> dig = ["00", "01", "10"];
static final List<String> dig1 = ["", "1", "10"];
}
 
void main() {
print("Addition:");
var g = Zeckendorf("10");
g + Zeckendorf("10");
print(g);
g + Zeckendorf("10");
print(g);
g + Zeckendorf("1001");
print(g);
g + Zeckendorf("1000");
print(g);
g + Zeckendorf("10101");
print(g);
 
print("\nSubtraction:");
g = Zeckendorf("1000");
g - Zeckendorf("101");
print(g);
g = Zeckendorf("10101010");
g - Zeckendorf("1010101");
print(g);
 
print("\nMultiplication:");
g = Zeckendorf("1001");
g * Zeckendorf("101");
print(g);
g = Zeckendorf("101010");
g + Zeckendorf("101");
print(g);
}
</syntaxhighlight>
{{out}}
<pre>
Addition:
101
1001
10101
100101
1010000
 
Subtraction:
1
1000000
 
Multiplication:
1000100
1000100
 
</pre>
 
 
=={{header|Elena}}==
{{trans|C++}}
ELENA 56.0x :
<syntaxhighlight lang="elena">import extensions;
 
Line 1,023 ⟶ 1,202:
};
int v := (dVal $shr (i * 2)) && 3;
v =>
0 { ^ self }
1 { ^ self }
2 {
ifnot ((dVal $shr ((i + 1) * 2)).allMask:(1))
{
^ self
Line 1,039 ⟶ 1,218:
3 {
int tmp := 3 $shl (i * 2);
tmp := tmp.xorbxor(-1);
dVal := dVal && tmp;
self.b((i+1)*2)
Line 1,059 ⟶ 1,238:
if (pos == 0) { ^ self.inc() };
ifnot((dVal $shr pos).allMask:(1))
{
dVal += (1 $shl pos);
Line 1,067 ⟶ 1,246:
else
{
dVal := dVal && (1 $shl pos).InvertedBInverted;
self.b(pos + 1);
int arg := pos - ((pos > 1) ? 2 : 1);
Line 1,076 ⟶ 1,255:
private c(int pos)
{
if ((dVal $shr pos).allMask:(1))
{
int tmp := 1 $shl pos;
tmp := tmp.xorbxor(-1);
dVal := dVal && tmp;
^ self
Line 1,103 ⟶ 1,282:
int mLen := 0;
n.readContent(ref dValint v, ref dLenint l);
m.readContent(ref mVal, ref mLen);
for(int GNdVal := 0, GN < (mLen + 1) * 2, GN += 1)v;
dLen := l;
 
for(int GN := 0; GN < (mLen + 1) * 2; GN += 1)
{
if ((mVal $shr GN).allMask:(1))
{
self.b(GN)
Line 1,120 ⟶ 1,302:
int mLen := 0;
n.readContent(ref dValint v, ref dLenint l);
m.readContent(ref mVal, ref mLen);
for(int GNdVal := 0, GN < (mLen + 1) * 2, GN += 1) v;
dLen := l;
for(int GN := 0; GN < (mLen + 1) * 2; GN += 1)
{
if ((mVal $shr GN).allMask:(1))
{
self.c(GN)
Line 1,131 ⟶ 1,316:
};
while (((dVal $shr (dLen*2)) && 3) == 0 || dLen == 0)
{
dLen -= 1
Line 1,139 ⟶ 1,324:
internal constructor product(ZeckendorfNumber n, ZeckendorfNumber m)
{
n.readContent(ref dValint v, ref dLenint l);
dVal := v;
dLen := l;
ZeckendorfNumber Na := m;
Line 1,146 ⟶ 1,334:
ZeckendorfNumber Nt := 0n;
for(int i := 0,; i < (dLen + 1) * 2,; i += 1)
{
if (((dVal $shr i) && 1) > 0)
{
Nr += Nb
Line 1,157 ⟶ 1,345:
};
Nr.readContent(ref dValv, ref dLenl);
dVal := v;
dLen := l;
}
Line 1,171 ⟶ 1,362:
{ ^ "0" };
string s := dig1[(dVal $shr (dLen * 2)) && 3];
int i := dLen - 1;
while (i >= 0)
{
s := s + dig[(dVal $shr (i * 2)) && 3];
i-=1
Line 2,449 ⟶ 2,640:
 
=={{header|Perl}}==
<syntaxhighlight lang="perl">#!/usr/bin/perluse v5.36;
 
package Zeckendorf;
use strict; # https://rosettacode.org/wiki/Zeckendorf_arithmetic
use overload qw("" zstring + zadd - zsub ++ zinc -- zdec * zmul / zdiv ge zge);
use warnings;
 
sub new ($class, $value) {
bless \$value, ref $class || $class;
}
 
sub zinc ($self, $, $) {
local $_ = $$self;
s/0$/1/ or s/(?:^|0)1$/10/;
1 while s/(?:^|0)11/100/;
$$self = $self->new( s/^0+\B//r )
}
 
sub zdec ($self, $, $) {
local $_ = $$self;
1 while s/100(?=0*$)/011/;
s/1$/0/ || s/10$/01/;
$$self = $self->new( s/^0+\B//r )
}
 
sub zadd ($self, $other, $) {
my ($x, $y) = map $self->new($$_), $self, $other;
$x++, $y-- while $$y;
$x
}
 
sub zsub ($self, $other, $) {
my ($x, $y) = map $self->new($$_), $self, $other;
$x--, $y-- while $$y;
$x
}
 
sub zmul ($self, $other, $) {
my ($x, $y) = map $self->new($$_), $self, $other;
my $product = Zeckendorf->new(0);
$product = $product + $x, $y-- while $y;
$product
}
 
sub zdiv ($self, $other, $) {
my ($x, $y) = map $self->new($$_), $self, $other;
my $quotient = Zeckendorf->new(0);
$quotient++, $x = $x - $y while $x ge $y;
$quotient
}
 
sub zge ($self, $other, $) {
my $l; $l = length $$other if length $other > ($l = length $$self);
0 x ($l - length $$self) . $$self ge 0 x ($l - length $$other) . $$other;
}
 
sub asdecimal ($self) {
my($aa, $bb, $n) = (1, 1, 0);
for ( reverse split '', $$self ) {
$n += $bb * $_;
($aa, $bb) = ($bb, $aa + $bb);
}
$n
}
 
sub fromdecimal ($self, $value) {
my $z = $self->new(0);
$z++ for 1 .. $value;
$z
}
 
sub zstring { ${ shift() } }
 
package main;
 
for ( split /\n/, <<END ) # test cases
Line 2,475 ⟶ 2,734:
$op eq '/' ? $x / $y :
die "bad op <$op>";
printf "%12s %s %-9s => %12s in Zeckendorf\n", $x, $op, $y, $answer;
printf "%12d %s %-9d => %12d in decimal\n\n",
$x->asdecimal, $op, $y->asdecimal, $answer->asdecimal;
}
 
package Zeckendorf;
use overload qw("" zstring + zadd - zsub ++ zinc -- zdec * zmul / zdiv ge zge);
 
sub new
{
my ($class, $value) = @_;
bless \$value, ref $class || $class;
}
 
sub zinc
{
my ($self, $other, $swap) = @_;
local $_ = $$self;
s/0$/1/ or s/(?:^|0)1$/10/;
1 while s/(?:^|0)11/100/;
$_[0] = $self->new( s/^0+\B//r );
}
 
sub zdec
{
my ($self, $other, $swap) = @_;
local $_ = $$self;
1 while s/100(?=0*$)/011/;
s/1$/0/ or s/10$/01/;
$_[0] = $self->new( s/^0+\B//r );
}
 
sub zstring { ${ shift() } }
 
sub zadd
{
my ($self, $other, $swap) = @_;
my ($x, $y) = map $self->new($$_), $self, $other; # copy
++$x, $y-- while $$y ne 0;
return $x;
}
 
sub zsub
{
my ($self, $other, $swap) = @_;
my ($x, $y) = map $self->new($$_), $self, $other; # copy
--$x, $y-- while $$y ne 0;
return $x;
}
 
sub zmul
{
my ($self, $other, $swap) = @_;
my ($x, $y) = map $self->new($$_), $self, $other; # copy
my $product = Zeckendorf->new(0);
$product = $product + $x, --$y while "$y" ne 0;
return $product;
}
 
sub zdiv
{
my ($self, $other, $swap) = @_;
my ($x, $y) = map $self->new($$_), $self, $other; # copy
my $quotient = Zeckendorf->new(0);
++$quotient, $x = $x - $y while $x ge $y;
return $quotient;
}
 
sub zge
{
my ($self, $other, $swap) = @_;
my $l = length( $$self | $$other );
0 x ($l - length $$self) . $$self ge 0 x ($l - length $$other) . $$other;
}
 
sub asdecimal
{
my ($self) = @_;
my $n = 0;
my $aa = my $bb = 1;
for ( reverse split //, $$self )
{
$n += $bb * $_;
($aa, $bb) = ($bb, $aa + $bb);
}
return $n;
}
 
sub fromdecimal
{
my ($self, $value) = @_;
my $z = $self->new(0);
++$z for 1 .. $value;
return $z;
}</syntaxhighlight>
{{out}}
<pre> 1 + 1 => 10 in Zeckendorf
<pre>
1 + 1 => 10 in Zeckendorf
1 + 1 => 2 in decimal
 
Line 2,600 ⟶ 2,767:
 
100001000001 / 100101 => 100010 in Zeckendorf
255 / 17 => 15 in decimal</pre>
 
</pre>
 
=={{header|Phix}}==
Line 3,258 ⟶ 3,423:
Subtraction is implemented as ''difference'' (i.e. abs(a-b) as this is an unsigned implementation.) The process is to reduce both numbers in value until the smaller one equals zero. Continuing the naming theme established by <code>canonise</code> and <code>defrock</code>, the word that removes the bits that are set to 1 in both arguments is called <code>exorcise</code>. The appropriate sequence of exorcisms and defrockings will reduce the smaller argument to zero much of the time.
 
However, numbers which alternate 1s and 0s (e.g. ...01010101...) are immune to both canonisation and defrocking). When this occurs we add the smaller number to the larger number and double the smaller number and repeat the exorisms and defrockings. Extensive testing leads me to believe with a very high degree of confidence this is sufficient, but I have not proved it in a mathematical sense.
 
Division is basic binary long division with a twist; instead of multiplying the divisor by 2 until it's large enough, use it to make a fibonacci style sequence, except starting with a couple of copies of the divisor rather than 1s.
Line 3,429 ⟶ 3,594:
else drop ] ] is zdivmod ( z z --> z z )
 
[ zdivmod drop ] is zdiv ( z z --> z )
 
[ zdivmod nip ] is zmod ( z z --> z )
 
[ [ dup while
tuck zmod again ]
drop ] is zgcd ( z z --> z )
 
[ 2dup and iff
Line 3,693 ⟶ 3,858:
=={{header|Raku}}==
(formerly Perl 6)
 
This is a somewhat limited implementation of Zeckendorf arithmetic operators. They only handle positive integer values. There are no actual calculations, everything is done with string manipulations, so it doesn't matter what glyphs you use for 1 and 0.
{{works with|rakudo|2019.03}}
 
Implemented arithmetic operators:
addition: '''+z''' addition
subtraction: '''-z''' subtraction
multiplication: '''*z×z''' multiplication
division: '''/z''' division (more of a divmod really)
post increment: '''++z''' post increment
post decrement: '''--z''' post decrement
 
Comparison operators:
equal '''eqz''' equal
not equal '''nez''' not equal
greater than '''gtz''' greater than
less than '''ltz''' less than
 
<syntaxhighlight lang="raku" line>my $z1 = '1'; # glyph to use for a '1'
my $z0 = '0'; # glyph to use for a '0'
 
sub zorder($a) { ($z0 lt $z1) ?? $a !! $a.trans([$z0, $z1] => [$z1, $z0]) };
 
######## Zeckendorf comparison operators #########
 
# less than
sub infix:<ltz>($a, $b) { $a.&zorder lt $b.&zorder };
 
# greater than
sub infix:<gtz>($a, $b) { $a.&zorder gt $b.&zorder };
 
# equal
sub infix:<eqz>($a, $b) { $a eq $b };
 
# not equal
sub infix:<nez>($a, $b) { $a ne $b };
 
######## Operators for Zeckendorf arithmetic ########
Line 3,748 ⟶ 3,913:
 
# addition
sub infix:<+z>($a is copy, $b is copy) { $a++z; $a++z while $b--z nez $z0; $a };
 
# subtraction
sub infix:<-z>($a is copy, $b is copy) { $a--z; $a--z while $b--z nez $z0; $a };
 
# multiplication
sub infix:<*z×z>($a, $b) {
return $z0 if $a eqz $z0 or $b eqz $z0;
return $a if $b eqz $z1;
Line 3,766 ⟶ 3,931:
} until $d eqz $b;
$c
};
 
# division (really more of a div mod)
Line 3,781 ⟶ 3,946:
$c ~= " remainder $a" if $a nez $z0;
$c
};
 
###################### Testing ######################
 
# helper sub to translate constants into the particular glyphs you used
sub z($a) { $a.trans([<1 0>] => [$z1, $z0]) };
 
say "Using the glyph '$z1' for 1 and '$z0' for 0\n";
Line 3,800 ⟶ 3,965:
printf $fmt, "$zeck -z {z('100')}", $zeck -z= z('100'), '# subtraction';
 
printf $fmt, "$zeck *z×z {z('100101')}", $zeck *z×z= z('100101'), '# multiplication';
 
printf $fmt, "$zeck /z {z('100')}", $zeck /z= z('100'), '# division';
Line 3,806 ⟶ 3,971:
printf( $fmt, "$zeck--z", $zeck--z, '# decrement' ) for 1 .. 5;
 
printf $fmt, "$zeck *z×z {z('101001')}", $zeck *z×z= z('101001'), '# multiplication';
 
printf $fmt, "$zeck /z {z('100')}", $zeck /z= z('100'), '# division';</syntaxhighlight>
Line 3,826 ⟶ 3,991:
10100 +z 1010 = 101000 # addition
101000 -z 100 = 100010 # subtraction
100010 *z×z 100101 = 100001000001 # multiplication
100001000001 /z 100 = 101010001 # division
101010001--z = 101010000 # decrement
Line 3,833 ⟶ 3,998:
101001001--z = 101001000 # decrement
101001000--z = 101000101 # decrement
101000101 *z×z 101001 = 101010000010101 # multiplication
101010000010101 /z 100 = 1001010001001 remainder 10 # division</pre>
Using alternate glyphs:
Output using 'X' for 1 and 'O' for 0:
<pre>
Using the glyph 'X' for 1 and 'O' for 0
Line 3,851 ⟶ 4,016:
XOXOO +z XOXO = XOXOOO # addition
XOXOOO -z XOO = XOOOXO # subtraction
XOOOXO *z×z XOOXOX = XOOOOXOOOOOX # multiplication
XOOOOXOOOOOX /z XOO = XOXOXOOOX # division
XOXOXOOOX--z = XOXOXOOOO # decrement
Line 3,858 ⟶ 4,023:
XOXOOXOOX--z = XOXOOXOOO # decrement
XOXOOXOOO--z = XOXOOOXOX # decrement
XOXOOOXOX *z×z XOXOOX = XOXOXOOOOOXOXOX # multiplication
XOXOXOOOOOXOXOX /z XOO = XOOXOXOOOXOOX remainder XO # division</pre>
 
=={{header|Rust}}==
{{trans|C#}}
<syntaxhighlight lang="Rust">
struct Zeckendorf {
d_val: i32,
d_len: i32,
}
 
impl Zeckendorf {
fn new(x: &str) -> Zeckendorf {
let mut d_val = 0;
let mut q = 1;
let mut i = x.len() as i32 - 1;
let d_len = i / 2;
while i >= 0 {
d_val += (x.chars().nth(i as usize).unwrap() as i32 - '0' as i32) * q;
q *= 2;
i -= 1;
}
 
Zeckendorf { d_val, d_len }
}
 
fn a(&mut self, n: i32) {
let mut i = n;
loop {
if self.d_len < i {
self.d_len = i;
}
let j = (self.d_val >> (i * 2)) & 3;
match j {
0 | 1 => return,
2 => {
if ((self.d_val >> ((i + 1) * 2)) & 1) != 1 {
return;
}
self.d_val += 1 << (i * 2 + 1);
return;
}
3 => {
let temp = 3 << (i * 2);
let temp = !temp;
self.d_val &= temp;
self.b((i + 1) * 2);
}
_ => (),
}
i += 1;
}
}
 
fn b(&mut self, pos: i32) {
if pos == 0 {
self.inc();
return;
}
if ((self.d_val >> pos) & 1) == 0 {
self.d_val += 1 << pos;
self.a(pos / 2);
if pos > 1 {
self.a(pos / 2 - 1);
}
} else {
let temp = 1 << pos;
let temp = !temp;
self.d_val &= temp;
self.b(pos + 1);
self.b(pos - if pos > 1 { 2 } else { 1 });
}
}
 
fn c(&mut self, pos: i32) {
if ((self.d_val >> pos) & 1) == 1 {
let temp = 1 << pos;
let temp = !temp;
self.d_val &= temp;
return;
}
self.c(pos + 1);
if pos > 0 {
self.b(pos - 1);
} else {
self.inc();
}
}
 
fn inc(&mut self) -> &mut Self {
self.d_val += 1;
self.a(0);
self
}
 
fn copy(&self) -> Zeckendorf {
Zeckendorf {
d_val: self.d_val,
d_len: self.d_len,
}
}
 
fn plus_assign(&mut self, other: &Zeckendorf) {
for gn in 0..(other.d_len + 1) * 2 {
if ((other.d_val >> gn) & 1) == 1 {
self.b(gn);
}
}
}
 
fn minus_assign(&mut self, other: &Zeckendorf) {
for gn in 0..(other.d_len + 1) * 2 {
if ((other.d_val >> gn) & 1) == 1 {
self.c(gn);
}
}
while (((self.d_val >> self.d_len * 2) & 3) == 0) || (self.d_len == 0) {
self.d_len -= 1;
}
}
 
fn times_assign(&mut self, other: &Zeckendorf) {
let mut na = other.copy();
let mut nb = other.copy();
let mut nt;
let mut nr = Zeckendorf::new("0");
for i in 0..(self.d_len + 1) * 2 {
if ((self.d_val >> i) & 1) > 0 {
nr.plus_assign(&nb);
}
nt = nb.copy();
nb.plus_assign(&na);
na = nt.copy(); // `na` is now mutable, so this reassignment is allowed
}
self.d_val = nr.d_val;
self.d_len = nr.d_len;
}
 
fn to_string(&self) -> String {
if self.d_val == 0 {
return "0".to_string();
}
 
let dig = ["00", "01", "10"];
let dig1 = ["", "1", "10"];
 
let idx = (self.d_val >> (self.d_len * 2)) & 3;
let mut sb = String::from(dig1[idx as usize]);
for i in (0..self.d_len).rev() {
let idx = (self.d_val >> (i * 2)) & 3;
sb.push_str(dig[idx as usize]);
}
sb
}
}
 
fn main() {
println!("Addition:");
let mut g = Zeckendorf::new("10");
g.plus_assign(&Zeckendorf::new("10"));
println!("{}", g.to_string());
g.plus_assign(&Zeckendorf::new("10"));
println!("{}", g.to_string());
g.plus_assign(&Zeckendorf::new("1001"));
println!("{}", g.to_string());
g.plus_assign(&Zeckendorf::new("1000"));
println!("{}", g.to_string());
g.plus_assign(&Zeckendorf::new("10101"));
println!("{}", g.to_string());
println!();
 
println!("Subtraction:");
g = Zeckendorf::new("1000");
g.minus_assign(&Zeckendorf::new("101"));
println!("{}", g.to_string());
g = Zeckendorf::new("10101010");
g.minus_assign(&Zeckendorf::new("1010101"));
println!("{}", g.to_string());
println!();
 
println!("Multiplication:");
g = Zeckendorf::new("1001");
g.times_assign(&Zeckendorf::new("101"));
println!("{}", g.to_string());
g = Zeckendorf::new("101010");
g.plus_assign(&Zeckendorf::new("101"));
println!("{}", g.to_string());
}
</syntaxhighlight>
{{out}}
<pre>
Addition:
101
1001
10101
100101
1010000
 
Subtraction:
1
1000000
 
Multiplication:
1000100
1000100
</pre>
=={{header|Scala}}==
{{works with|Scala|2.13.1}}
Line 4,751 ⟶ 5,119:
{{trans|Kotlin}}
{{libheader|Wren-trait}}
<syntaxhighlight lang="ecmascriptwren">import "./trait" for Comparable
 
class Zeckendorf is Comparable {
Alextretyak
1,480

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/334309...364325"