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
