Zeckendorf arithmetic: Difference between revisions

 

[http://arxiv.org/pdf/1207.4497.pdf Efficient algorithms for Zeckendorf arithmetic] is interesting. The sections on addition and subtraction are particularly relevant for this task.

 

=={{header|C}}==

{{trans|D}}

#include <stdio.h>

#include <string.h>

 

return 0;

{{out}}

<pre>Addition:

=={{header|C sharp|C#}}==

{{trans|Java}}

using System.Text;

 

}

}

{{out}}

<pre>Addition:

=={{header|C++}}==

{{works with|C++11}}

// I define an increment operation ++()

// I define a comparison operation <=(other N)

return os;

}

===Testing===

The following tests addtition:

N G;

G = 10N;

std::cout << G << std::endl;

return 0;

{{out}}

<pre>

</pre>

The following tests subtraction:

N G;

G = 1000N;

std::cout << G << std::endl;

return 0;

{{out}}

<pre>

</pre>

The following tests multiplication:

int main(void) {

N G = 1001N;

std::cout << G << std::endl;

return 0;

{{out}}

<pre>

=={{header|D}}==

{{trans|Kotlin}}

 

int inv(int a) {

g += "101".Z;

writeln(g);

{{out}}

<pre>Addition:

1000100

1000100</pre>

 

=={{header|Elena}}==

{{trans|C++}}

 

const dig = new string[]{"00","01","10"};

};

v =>

0 { ^ self }

1 { ^ self }

2 {

{

^ self

3 {

int tmp := 3 $shl (i * 2);

self.b((i+1)*2)

if (pos == 0) { ^ self.inc() };

{

dVal += (1 $shl pos);

else

{

self.b(pos + 1);

int arg := pos - ((pos > 1) ? 2 : 1);

private c(int pos)

{

{

int tmp := 1 $shl pos;

^ self

int mLen := 0;

m.readContent(ref mVal, ref mLen);

{

{

self.b(GN)

int mLen := 0;

m.readContent(ref mVal, ref mLen);

{

{

self.c(GN)

};

{

dLen -= 1

internal constructor product(ZeckendorfNumber n, ZeckendorfNumber m)

{

ZeckendorfNumber Na := m;

ZeckendorfNumber Nt := 0n;

{

{

Nr += Nb

};

}

{ ^ "0" };

int i := dLen - 1;

while (i >= 0)

{

i-=1

n += 101n;

console.printLine(n)

{{out}}

<pre>

=={{header|Go}}==

{{trans|Kotlin}}

 

import (

g.PlusAssign(NewZeck("101"))

fmt.Println(g)

 

{{out}}

1000100

</pre>

 

=={{header|Java}}==

{{trans|Kotlin}}

{{works with|Java|9}}

 

public class Zeckendorf implements Comparable<Zeckendorf> {

System.out.println(g);

}

{{out}}

<pre>Addition:

=={{header|Julia}}==

Influenced by the format of the Tcl and Raku versions, but added other functionality.

 

const z0 = "0"

 

zeckendorftest()

Addition:

101

=={{header|Kotlin}}==

{{trans|C++}}

 

class Zeckendorf(x: String = "0") : Comparable<Zeckendorf> {

g += "101".Z

println(g)

 

{{out}}

</pre>

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

{{out}}

<pre>

 

=={{header|PicoLisp}}==

 

(de unpad (Lst)

(test (numz (- X 1)) (decz (numz X))) ) )

 

 

=={{header|Python}}==

 

class Zeckendorf:

g = Zeckendorf("101010")

g = g + Zeckendorf("101")

{{out}}

<pre>Addition:

1000100

1000100</pre>

 

=={{header|Racket}}==

This implementation only handles natural (non-negative numbers). The algorithms for addition and subtraction use the techniques explained in the paper "Efficient algorithms for Zeckendorf arithmetic" (http://arxiv.org/pdf/1207.4497.pdf).

 

 

(define sqrt5 (sqrt 5))

(example '/ zeck-quotient 9876 1000)

(example '% zeck-remainder 9876 1000)

 

{{output}}

=={{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.

 

Implemented arithmetic operators:

 

Comparison operators:

 

my $z0 = '0'; # glyph to use for a '0'

 

 

######## Zeckendorf comparison operators #########

 

# less than

 

# greater than

 

# equal

 

# not equal

 

######## Operators for Zeckendorf arithmetic ########

 

# addition

 

# subtraction

 

# multiplication

return $z0 if $a eqz $z0 or $b eqz $z0;

return $a if $b eqz $z1;

} until $d eqz $b;

$c

 

# division (really more of a div mod)

$c ~= " remainder $a" if $a nez $z0;

$c

 

###################### Testing ######################

 

# helper sub to translate constants into the particular glyphs you used

 

say "Using the glyph '$z1' for 1 and '$z0' for 0\n";

printf $fmt, "$zeck -z {z('100')}", $zeck -z= z('100'), '# subtraction';

 

 

printf $fmt, "$zeck /z {z('100')}", $zeck /z= z('100'), '# division';

printf( $fmt, "$zeck--z", $zeck--z, '# decrement' ) for 1 .. 5;

 

 

 

'''Testing Output'''

10100 +z 1010 = 101000 # addition

101000 -z 100 = 100010 # subtraction

100001000001 /z 100 = 101010001 # division

101010001--z = 101010000 # decrement

101001001--z = 101001000 # decrement

101001000--z = 101000101 # decrement

101010000010101 /z 100 = 1001010001001 remainder 10 # division</pre>

<pre>

Using the glyph 'X' for 1 and 'O' for 0

XOXOO +z XOXO = XOXOOO # addition

XOXOOO -z XOO = XOOOXO # subtraction

XOOOOXOOOOOX /z XOO = XOXOXOOOX # division

XOXOXOOOX--z = XOXOXOOOO # decrement

XOXOOXOOX--z = XOXOOXOOO # decrement

XOXOOXOOO--z = XOXOOOXOX # decrement

XOXOXOOOOOXOXOX /z XOO = XOOXOXOOOXOOX remainder XO # division</pre>

 

=={{header|Scala}}==

{{works with|Scala|2.13.1}}

The addition is an implementation of an algorithm suggested in http[:]//arxiv.org/pdf/1207.4497.pdf: Efficient Algorithms for Zeckendorf Arithmetic.

import scala.collection.mutable.ListBuffer

 

 

}

Output:

<pre style="height: 30ex; overflow: scroll">101Z(i:4) + 10100Z(i:11) = 100010Z(i:15)

=={{header|Tcl}}==

{{trans|Raku}}<!-- mostly for the technique of using incr/decr -->

# Want to use alternate symbols? Change these

variable zero "0"

namespace export \[a-y\]*

namespace ensemble create

Demonstrating:

puts [zeckendorf sub "10100" "1010"]

puts [zeckendorf mul "10100" "1010"]

puts [zeckendorf div "10100" "1010"]

{{out}}

<pre>

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Module Module1

End Sub

 

{{out}}

<pre>Addition:

1000100

1000100</pre>

 

=={{header|Wren}}==

{{trans|Kotlin}}

{{libheader|Wren-trait}}

 

class Zeckendorf is Comparable {

g = Z.new("101010")

g.plusAssign(Z.new("101"))

 

{{out}}