Puzzles/Exp With Sub

From J Wiki
Jump to: navigation, search

TableOfContents

Find an expression for the sequence  \{ x \, k^i \}_{ i=0 \dots N-1 }, for any x \in \mathbf{R}; \, k, N \in \mathbf{N}. E.g.

   7.5*5^i.8   NB. x*k^i.N
7.5 37.5 187.5 937.5 4687.5 23437.5 117188 585938

using subtraction (dyadic -) as the only numeric operation. That is only structural operations are allowed besides constants (i. or @. are OK, m o. or m b. are not). The expression should not use any constants other than the three x, k and N.

The time/space performance can be better than the original expression x*k^i.N, which is especially visible with large N>1000.









Spoiler Alert!















Solutions

   plus=: - 0&-
   times=: 4 :'x. plus ^:y. 0'
   sequence=: 4 :0
'k N'=.y.
x.times k times^:(i.N) 1
)
   7.5 sequence 5 8
7.5 37.5 187.5 937.5 4687.5 23437.5 117188 585938

By [|Raul_Miller]]

This solution with N=12 gives out of memory. -- Oleg Kobchenko DateTime(2006-01-26T23:49:39Z)


   plus =: [ - -~@[ - ]
   times=: plus /@$~"0  NB. x+i
   pow  =: times/@$~"0  NB. x^i

   7.5 times times/\ 1,7$5
7.5 37.5 187.5 937.5 4687.5 23437.5 117188 585938

   7.5 times 5 pow i.8
7.5 37.5 187.5 937.5 4687.5 23437.5 117188 585938

By Roger Hui

With N=12 on 256 Mb limit this solution gives limit error. -- Oleg Kobchenko DateTime(2006-01-26T23:49:39Z)


I forgot the initial solution, which was reversed into this puzzle, and gave better performance than the direct expression. It was very simple and quite non-trivial.

Here's some ideas -- worse that the direct expression by slightly less than an order both in time and space. But they both emulate +, whereas in the original - with previous value of the sequence was used in a simpler manner.

This one emulates * with +/@$ as in Roger's solution.

   5 (- (-~ -~))/@$^:(<8) 7.5
7.5 37.5 187.5 937.5 4687.5 23437.5 117188 585938

Here * is done with the hook (+^: 0:)

   ((- (-~ -~))^:5 -~)^:(<8) 7.5
7.5 37.5 187.5 937.5 4687.5 23437.5 117188 585938

What is captured and different from other solutions, is that the order of multiplication is

 ... * 5 * 5 * 7.5 , rather than

 7.5 * 5 * 5 * ... .

-- Oleg Kobchenko DateTime(2006-02-06T07:22:19Z)


Contributed by Oleg Kobchenko