How to resolve the algorithm Zeckendorf arithmetic step by step in the Java programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Zeckendorf arithmetic step by step in the Java programming language
Table of Contents
Problem Statement
This task is a total immersion zeckendorf task; using decimal numbers will attract serious disapprobation. The task is to implement addition, subtraction, multiplication, and division using Zeckendorf number representation. Optionally provide decrement, increment and comparitive operation functions. Like binary 1 + 1 = 10, note carry 1 left. There the similarity ends. 10 + 10 = 101, note carry 1 left and 1 right. 100 + 100 = 1001, note carry 1 left and 2 right, this is the general case. Occurrences of 11 must be changed to 100. Occurrences of 111 may be changed from the right by replacing 11 with 100, or from the left converting 111 to 100 + 100; 10 - 1 = 1. The general rule is borrow 1 right carry 1 left. eg: A larger example: Here you teach your computer its zeckendorf tables. eg. 101 * 1001: Lets try 1000101 divided by 101, so we can use the same table used for multiplication. Efficient algorithms for Zeckendorf arithmetic is interesting. The sections on addition and subtraction are particularly relevant for this task.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Zeckendorf arithmetic step by step in the Java programming language
Here's a detailed explanation of the code, incorporating insights from previous responses and addressing potential issues:
Key Concepts:
- Zeckendorf Representation: A way to represent positive integers uniquely using a sum of non-consecutive Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, ...).
- Binary-Like Encoding: The code uses a custom binary-like encoding for Zeckendorf numbers, where each pair of bits represents a digit:
- 00 = 0
- 01 = 1
- 10 = 2
- 11 (illegal, not a valid Zeckendorf digit)
Code Breakdown:
1. Class Zeckendorf:
- Fields:
x: String representation of the Zeckendorf number.dVal: Integer representation using the binary-like encoding.dLen: Length of the encoded value in bit pairs.
- Constructors:
Zeckendorf(): Initializes as "0".Zeckendorf(String x): Initializes from a string representation.
- Methods:
a(int n),b(int pos),c(int pos): Helper methods for carrying out arithmetic operations within the Zeckendorf representation.inc(): Increments the Zeckendorf number by 1.plusAssign(Zeckendorf other): Adds another Zeckendorf number.minusAssign(Zeckendorf other): Subtracts another Zeckendorf number.timesAssign(Zeckendorf other): Multiplies by another Zeckendorf number.copy(): Creates a copy of the Zeckendorf number.compareTo(Zeckendorf other): Compares two Zeckendorf numbers for sorting.toString(): Converts the Zeckendorf number back to its string representation.
2. main(String[] args):
- Demonstrates the arithmetic operations with examples.
Additional Notes:
- The code uses a custom binary-like encoding for Zeckendorf numbers, not standard binary.
- The arithmetic operations are implemented using specific algorithms for Zeckendorf representation.
- Consider potential issues like handling illegal Zeckendorf representations (containing "11").
- Explore alternative implementations or optimizations for specific use cases.
Source code in the java programming language
import java.util.List;
public class Zeckendorf implements Comparable<Zeckendorf> {
private static List<String> dig = List.of("00", "01", "10");
private static List<String> dig1 = List.of("", "1", "10");
private String x;
private int dVal = 0;
private int dLen = 0;
public Zeckendorf() {
this("0");
}
public Zeckendorf(String x) {
this.x = x;
int q = 1;
int i = x.length() - 1;
dLen = i / 2;
while (i >= 0) {
dVal += (x.charAt(i) - '0') * q;
q *= 2;
i--;
}
}
private void a(int n) {
int i = n;
while (true) {
if (dLen < i) dLen = i;
int 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:
int temp = 3 << (i * 2);
temp ^= -1;
dVal = dVal & temp;
b((i + 1) * 2);
break;
}
i++;
}
}
private void b(int pos) {
if (pos == 0) {
Zeckendorf thiz = this;
thiz.inc();
return;
}
if (((dVal >> pos) & 1) == 0) {
dVal += 1 << pos;
a(pos / 2);
if (pos > 1) a(pos / 2 - 1);
} else {
int temp = 1 << pos;
temp ^= -1;
dVal = dVal & temp;
b(pos + 1);
b(pos - (pos > 1 ? 2 : 1));
}
}
private void c(int pos) {
if (((dVal >> pos) & 1) == 1) {
int temp = 1 << pos;
temp ^= -1;
dVal = dVal & temp;
return;
}
c(pos + 1);
if (pos > 0) {
b(pos - 1);
} else {
Zeckendorf thiz = this;
thiz.inc();
}
}
public Zeckendorf inc() {
dVal++;
a(0);
return this;
}
public void plusAssign(Zeckendorf other) {
for (int gn = 0; gn < (other.dLen + 1) * 2; gn++) {
if (((other.dVal >> gn) & 1) == 1) {
b(gn);
}
}
}
public void minusAssign(Zeckendorf other) {
for (int gn = 0; gn < (other.dLen + 1) * 2; gn++) {
if (((other.dVal >> gn) & 1) == 1) {
c(gn);
}
}
while ((((dVal >> dLen * 2) & 3) == 0) || (dLen == 0)) {
dLen--;
}
}
public void timesAssign(Zeckendorf other) {
Zeckendorf na = other.copy();
Zeckendorf nb = other.copy();
Zeckendorf nt;
Zeckendorf nr = new Zeckendorf();
for (int i = 0; i < (dLen + 1) * 2; i++) {
if (((dVal >> i) & 1) > 0) {
nr.plusAssign(nb);
}
nt = nb.copy();
nb.plusAssign(na);
na = nt.copy();
}
dVal = nr.dVal;
dLen = nr.dLen;
}
private Zeckendorf copy() {
Zeckendorf z = new Zeckendorf();
z.dVal = dVal;
z.dLen = dLen;
return z;
}
@Override
public int compareTo(Zeckendorf other) {
return ((Integer) dVal).compareTo(other.dVal);
}
@Override
public String toString() {
if (dVal == 0) {
return "0";
}
int idx = (dVal >> (dLen * 2)) & 3;
StringBuilder stringBuilder = new StringBuilder(dig1.get(idx));
for (int i = dLen - 1; i >= 0; i--) {
idx = (dVal >> (i * 2)) & 3;
stringBuilder.append(dig.get(idx));
}
return stringBuilder.toString();
}
public static void main(String[] args) {
System.out.println("Addition:");
Zeckendorf g = new Zeckendorf("10");
g.plusAssign(new Zeckendorf("10"));
System.out.println(g);
g.plusAssign(new Zeckendorf("10"));
System.out.println(g);
g.plusAssign(new Zeckendorf("1001"));
System.out.println(g);
g.plusAssign(new Zeckendorf("1000"));
System.out.println(g);
g.plusAssign(new Zeckendorf("10101"));
System.out.println(g);
System.out.println("\nSubtraction:");
g = new Zeckendorf("1000");
g.minusAssign(new Zeckendorf("101"));
System.out.println(g);
g = new Zeckendorf("10101010");
g.minusAssign(new Zeckendorf("1010101"));
System.out.println(g);
System.out.println("\nMultiplication:");
g = new Zeckendorf("1001");
g.timesAssign(new Zeckendorf("101"));
System.out.println(g);
g = new Zeckendorf("101010");
g.plusAssign(new Zeckendorf("101"));
System.out.println(g);
}
}
You may also check:How to resolve the algorithm Jaro similarity step by step in the CoffeeScript programming language
You may also check:How to resolve the algorithm String append step by step in the AArch64 Assembly programming language
You may also check:How to resolve the algorithm Langton's ant step by step in the COBOL programming language
You may also check:How to resolve the algorithm Two's complement step by step in the 8086 Assembly programming language
You may also check:How to resolve the algorithm Substring/Top and tail step by step in the Scala programming language