Puzzles/Exp With Sub
Find an expression for the sequence , for any . 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