Rosetta Code

Zeckendorf arithmetic: Difference between revisions

Page Discussion

Zeckendorf arithmetic (view source)

Revision as of 09:13, 7 May 2024

8,353 bytes added ,  13 days ago
m
→‎{{header|11l}}: Void
imported>Arakov
 
(3 intermediate revisions by 2 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}}==
Line 3,847 ⟶ 4,026:
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,737 ⟶ 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/351757...364325"