Interseting!
encode 7 4 1776
]���
decode encode 7 4 1776
7 4 1776
Also:
f2=:13 :'{."1([:+/\|.)^:(i.y)1 1'
Fibs2=: 13 :'}.f2 y'
Fibs2 10
1 2 3 5 8 13 21 34 55
(genfibs 1400)-:Fibs2 1400
1
1
1
On to understand encode and decode.
-----Original Message-----
From: Programming <[email protected]> On Behalf Of 'Jon
Hough' via Programming
Sent: Thursday, July 18, 2019 10:46 AM
To: Programming Forum <[email protected]>
Subject: [Jprogramming] Fibonacci Encoding
Positive integers can be encoded using Fibonacci numbers.
For the sake of easer, assume Fibonacci numbers are 1,2,3,5,... (only one 1).
We can encode a positive integer uniquely using non-consecutive Fibonacci
numbers. For example
4 = 1 + 3 (note: 1 and 3 a re non-consecutive)
5 = 5 (already a Fib number)
6 = 1 + 5
7 = 2 + 5
8 = 8
These representation can be encoded using bits. 1's where a Fibonacci number is
in the representation, 0s when not.
4 = 1 + 3 = 101
5 = 0001
6 = 1001
7 = 0101
8 = 00001
...
We can append a 1 on the end of the encoding a a delimiter, so that during
decoding we know easily where to stop. This way integers can be packed together.
Here are some J verbs for encoding and decoding positive integers.
NB. ===================================================================
genfibs=: 3 : 0
r=. 1 2
i1=. 1
i2=. 2
c=. 2
while. y > c=. c+1 do.
t=. i1 + i2
i1=. i2
i2=. t
r=. r, x: t
end.
)
Fibs=: genfibs 1400
encode=: 3 : 0
d=. > (>@:,&:>)/ (<@encode1)"0 y
r=. d,'0' #~ (#d) -~ 8 * >. 8 %~ # d
pack r
)
encode1=: 3 : 0
n=. x: y
r=. ''
k=: ''
fl=. x: Fibs{~ I. Fibs <: y
i=. <:#fl
while. n do.
r=. r,'1'
n=. n- i{fl
k=: k,i{fl
i=. i-1
while. (i >: 0) *. (n<i{fl) do.
r=. r,'0'
i=. i-1
end.
end.
(|.r),'1'
)
pack=: 3 : 0
a.{~ #. _8 ] \"."0 y
)
decode=: 3 : 0
i=. , {:|."1 (8 # 2) ,:|."1 #: a.i. y
n=. ''
while. 1 e. 1 1 E. i do.
idx=. {. I. 1 1 E. i
n=. n, +/ Fibs {~ I. i {~ i. >: idx
i=. (2+idx) }. i
end.
n
)
NB. ===================================================================
The encode verb outputs the Fib-representation as bytes.
encode 4
#: a.i. encode 4
1 0 1 1 0 0 0 0
decode encode 449239438124834384923493383837734733747181x
449239438124834384923493383837734733747181
decode encode 1 2 3 4 5 6 7
1 2 3 4 5 6 7
Fibonacci encoding is not really a good compression encoding, but has some good
error handling properties.
I am not happy with the decode verb, as I wanted to write it without a while
loop. Difficult though as there are some awkaward consecutive bits that might
appear in the encoding, e.g.
...0 1 1 1 0...
Using 1 1 E. with this breaks decoding unless done carefully. Easier just to
use a while loop and eat the input every iteration.
refs:
https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FFibonacci_coding&data=02%7C01%7C%7Caa0f5ddb21594beef62008d70b8eadb2%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636990579736889714&sdata=kcs3aC0f7iTcRIMxGWQZR86jnPCYkTd8iCuApVi%2F7H4%3D&reserved=0
https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FZeckendorf%2527s_theorem&data=02%7C01%7C%7Caa0f5ddb21594beef62008d70b8eadb2%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636990579736889714&sdata=ek%2BmuGj5JjX6ls2x7PFOgSSjjWXu%2FehQouqHabjTjQ8%3D&reserved=0
----------------------------------------------------------------------
For information about J forums see
https://eur03.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.jsoftware.com%2Fforums.htm&data=02%7C01%7C%7Caa0f5ddb21594beef62008d70b8eadb2%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636990579736889714&sdata=9LaJ2RSPcE3LbxIr2XtWQatyJFgMC%2F%2FmOpt2VhsiSrw%3D&reserved=0
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
