How to resolve the algorithm Zeckendorf arithmetic step by step in the 11l programming language

Published on 12 May 2024 09:40 PM
#11l

How to resolve the algorithm Zeckendorf arithmetic step by step in the 11l 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 11l programming language

Source code in the 11l programming language

T Zeckendorf
   Int dLen
   dVal = 0

   F (x = ‘0’)
      V q = 1
      V i = x.len - 1
      .dLen = i I/ 2
      L i >= 0
         .dVal = .dVal + (x[i].code - ‘0’.code) * q
         q = q * 2
         i = i - 1

   F a(n)
      V i = n
      L
         I .dLen < i
            .dLen = i
         V j = (.dVal >> (i * 2)) [&] 3
         I j == 0 | j == 1
            R
         I j == 2
            I (.dVal >> ((i + 1) * 2) [&] 1) != 1
               R
            .dVal = .dVal + (1 << (i * 2 + 1))
            R
         I j == 3
            V temp = 3 << (i * 2)
            temp = temp (+) -1
            .dVal = .dVal [&] temp
            .b((i + 1) * 2)
         i = i + 1

   F b(pos)
      I pos == 0
         .inc()
         R
      I (.dVal >> pos) [&] 1 == 0
         .dVal = .dVal + (1 << pos)
         .a(Int(pos / 2))
         I pos > 1
            .a(Int(pos / 2) - 1)
      E
         V temp = 1 << pos
         temp = temp (+) -1
         .dVal = .dVal [&] temp
         .b(pos + 1)
         .b(pos - (I pos > 1 {2} E 1))

   F c(pos)
      I (.dVal >> pos) [&] 1 == 1
         V temp = 1 << pos
         temp = temp (+) -1
         .dVal = .dVal [&] temp
         R
      .c(pos + 1)
      I pos > 0
         .b(pos - 1)
      E
         .inc()

   F inc() -> N
      .dVal = .dVal + 1
      .a(0)

   F +(rhs)
      V copy = (.)
      V rhs_dVal = rhs.dVal
      V limit = (rhs.dLen + 1) * 2
      L(gn) 0 .< limit
         I ((rhs_dVal >> gn) [&] 1) == 1
            copy.b(gn)
      R copy

   F -(rhs)
      V copy = (.)
      V rhs_dVal = rhs.dVal
      V limit = (rhs.dLen + 1) * 2
      L(gn) 0 .< limit
         I (rhs_dVal >> gn) [&] 1 == 1
            copy.c(gn)
      L (((copy.dVal >> ((copy.dLen * 2) [&] 31)) [&] 3) == 0) | (copy.dLen == 0)
         copy.dLen = copy.dLen - 1
      R copy

   F *(rhs)
      V na = copy(rhs)
      V nb = copy(rhs)
      V nr = Zeckendorf()
      V dVal = .dVal
      L(i) 0 .< (.dLen + 1) * 2
         I ((dVal >> i) [&] 1) > 0
            nr = nr + nb
         V nt = copy(nb)
         nb = nb + na
         na = copy(nt)
      R nr

   F String()
      V dig = [‘00’, ‘01’, ‘10’]
      V dig1 = [‘’, ‘1’, ‘10’]

      I .dVal == 0
         R ‘0’
      V idx = (.dVal >> ((.dLen * 2) [&] 31)) [&] 3
      String sb = dig1[idx]
      V i = .dLen - 1
      L i >= 0
         idx = (.dVal >> (i * 2)) [&] 3
         sb ‘’= dig[idx]
         i = i - 1
      R sb

print(‘Addition:’)
V g = Zeckendorf(‘10’)
g = g + Zeckendorf(‘10’)
print(g)
g = g + Zeckendorf(‘10’)
print(g)
g = g + Zeckendorf(‘1001’)
print(g)
g = g + Zeckendorf(‘1000’)
print(g)
g = g + Zeckendorf(‘10101’)
print(g)
print()

print(‘Subtraction:’)
g = Zeckendorf(‘1000’)
g = g - Zeckendorf(‘101’)
print(g)
g = Zeckendorf(‘10101010’)
g = g - Zeckendorf(‘1010101’)
print(g)
print()

print(‘Multiplication:’)
g = Zeckendorf(‘1001’)
g = g * Zeckendorf(‘101’)
print(g)
g = Zeckendorf(‘101010’)
g = g + Zeckendorf(‘101’)
print(g)

You may also check:How to resolve the algorithm Globally replace text in several files step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm Count in octal step by step in the Delphi programming language
You may also check:How to resolve the algorithm Pascal's triangle step by step in the Mathematica/Wolfram Language programming language
You may also check:How to resolve the algorithm Create an HTML table step by step in the Lasso programming language
You may also check:How to resolve the algorithm Benford's law step by step in the Stata programming language