Just time to list d2z, dec to Zeckendorf...
_8{.Fb NB. Reverse list of fibs...
34 21 13 8 5 3 2 1
d2z. NB. Dec to z
3 : 0
f =. Fb, 0
if. y = 0 do. ,0 return. end.
if. y e. f do. (#~>./\ ) Fb = y return.end.
reduce =. | }. +/\ inv f&(( (] - I.{[)^:a:)) n =. y NB. 12 ==> 12 4 1
}: (#~>./\ ) f e. reduce
)
More later,
Mike
Sent from my iPad
> On 19 Jul 2019, at 11:07, Mike Day <[email protected]> wrote:
>
> I did a quick compare - on the hoof, so briefly- my d2z and z2d, ie
> decimal-Zeckendorf switches appear faster than decode/encode - no time to say
> how or why!
>
> More later,
>
> Mike
>
> Sent from my iPad
>
>> On 19 Jul 2019, at 01:26, 'Jon Hough' via Programming
>> <[email protected]> wrote:
>>
>> The encoding follows the following algorithm:
>>
>> "To encode an integer N:
>>
>> Find the largest Fibonacci number equal to or less than N; subtract this
>> number from N, keeping track of the remainder.
>> If the number subtracted was the ith Fibonacci number F(i), put a 1 in place
>> i−2 in the code word (counting the left most digit as place 0).
>> Repeat the previous steps, substituting the remainder for N, until a
>> remainder of 0 is reached.
>> Place an additional 1 after the rightmost digit in the code word.
>> To decode a code word, remove the final "1", assign the remaining the values
>> 1,2,3,5,8,13... (the Fibonacci numbers) to the bits in the code word, and
>> sum the values of the "1" bits."
>> see: https://en.wikipedia.org/wiki/Fibonacci_coding
>>
>>
>> It might not be the most elegant or terse verb, but I think there is not
>> much complexity in it. You are right that there is no need to use char
>> sequence, could just use integer list, which may or may not be fast. I
>> really did that for debugging purposes, to easily read the representation
>> while encoding. On Friday, July 19, 2019, 1:13:18 AM GMT+9, Raul Miller
>> <[email protected]> wrote:
>>
>> I'm not quite sure I understand your encoding scheme.
>>
>> Specifically, you're encoding into a sequence of characters, but when
>> decoding, you're not using (8#2)#:a.i.y and it looks like you've
>> cooked up some mechanism to compensate for how |."1#: behaves ...
>>
>> In other words, I think that the fibonacci encoding aspect isn't the
>> problem here.
>>
>> So I think I would start with either a careful description of your
>> "encode to character" mechanism (how can I know if you've implemented
>> what you intended without that? I'd rather not try to reverse engineer
>> your thoughts and assumptions if that's not necessary) or I would
>> start with an implementation which isn't so complicated.
>>
>> Thanks,
>>
>> --
>> Raul
>>
>> On Thu, Jul 18, 2019 at 10:46 AM 'Jon Hough' via Programming
>> <[email protected]> wrote:
>>>
>>> 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://en.wikipedia.org/wiki/Fibonacci_coding
>>> https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem
>>> ----------------------------------------------------------------------
>>> For information about J forums see http://www.jsoftware.com/forums.htm
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
