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
