"In other words, it's not the fibonacci part that's the problem for me, it's whatever you are using to convert to ascii that's the problem.
(Note also that there's no need to add any 1s into the represented result - you just terminate the sequence by eliminating what would be trailing ascii nul characters.) Am I making any sense here?" Sorry, I am struggling to understand your point. Converting to ASCII is just to pack the bytes. It seems more purposeful than leaving as an array of 0s and 1s. It isn't a necessary step, but in an imaginary world where I want to encode a list of positive integers using Fibonacci Encoding and send them over the wire to someone else, I would probably convert to ASCII (i.e. get byte representation) and then Base64 encode that result, and reverse on the other end. Also, the final 1 is not necessary, as you mentioned, if I am only encoding a single integer. But the encoding scheme specifically states to do this, and what's more I am also encoding a series of ints. So there needs to be a "separator" between the eoncdings. The "1 1" pattern seems the most natural as it is impossible to have two consecutive 1's in a Fibonacci encoding of any given integer. load 'convert/misc/base64' # tobase64 encode >: i. 100 gives 148 bytes, which is probably not bad in terms of compression. decode frombase64 tobase64 encode >: i.100 gives the precise ints again, as one would hope for. I am not claiming this is a useful encoding, but it is quite an interesting way of representing integers. On Saturday, July 20, 2019, 12:32:27 AM GMT+9, Raul Miller <[email protected]> wrote: I understand the fibonacci aspect. Using Roger Hui's code: ,.fsum 449239438124834384923493383837734733747181x 280571172992510140037611932413038677189525 107168651819712326877926895128666735145224 40934782466626840596168752972961528246147 15635695580168194910579363790217849593217 3691087032412706639440686994833808526209 871347450517368352816615810882615488381 332825110087067562321196029789634457848 30010821454963453907530667147829489881 2706074082469569338358691163510069157 1033628323428189498226463595560281832 93202207781383214849429075266681969 22002056689466296922983322104048463 8404037832974134882743767626780173 1226132595394188293000174702095995 289450641941273985495088042104137 16130531424904581415797907386349 6161314747715278029583501626149 2353412818241252672952597492098 343358302784187294870275058337 50095301248058391139327916261 11825896447871834976429068427 2791715456571051233611642553 5358359254990966640871840 1264937032042997393488322 483162952612010163284885 184551825793033096366333 70492524767089125814114 6356306993006846248183 83621143489848422977 31940434634990099905 1100087778366101931 420196140727489673 99194853094755497 8944394323791464 2111485077978050 806515533049393 308061521170129 72723460248141 27777890035288 4052739537881 1548008755920 591286729879 225851433717 53316291173 20365011074 4807526976 701408733 267914296 102334155 39088169 5702887 2178309 196418 28657 4181 233 55 8 3 And, I understand mapping this to a bit sequence which can be represented as a byte sequence: 0 8#:1 i:~Fibs e.fsum 449239438124834384923493383837734733747181x 24 6 25 8$Fibs e.fsum 449239438124834384923493383837734733747181x 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 And, I can verify that this was accurate: +/x:Fibs#~Fibs e.fsum 449239438124834384923493383837734733747181x 449239438124834384923493383837734733747181 But I do not see how to get from there to what you're doing: (8#2)#:a.i.encode 449239438124834384923493383837734733747181x 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 1 In other words, it's not the fibonacci part that's the problem for me, it's whatever you are using to convert to ascii that's the problem. (Note also that there's no need to add any 1s into the represented result - you just terminate the sequence by eliminating what would be trailing ascii nul characters.) Am I making any sense here? Thanks, -- Raul On Thu, Jul 18, 2019 at 8:26 PM '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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
