A surprisingly easy binary search: start at one and double it until you go too
high. Then you have an interval whose length is a power of two that you know
the number is in. Halve this interval and pick the right side until you find
something that matches your number.
For both findmax and binsearch, x is the number being searched for. For
findmax, y is the starting number (probably 1), and for binsearch, it is the
interval (ie. (128 256)).
findmax=. +:@]^:(>f)^:_ NB. search for higher bound of the interval; bound
will consist of this number and the previous (ie. half of it).
midpt=. -:@+/@]
binsearch=. midpt`(midpt,{:@])`({...@],midpt) @.(*...@- f...@midpt)
^:(2...@])^:_
g=. ([ binsearch [: (,~-:) findmax)&1
6!:2'g 6037'
0.0299741
6!:2'g 60000'
0.565413
g2=:((>:@:])^:([>f@:])^:_)~
6!:2'g2 6037'
0.134958
6!:2'g2 60000'
9.70725
Marshall
-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of bob therriault
Sent: Sunday, December 26, 2010 7:21 PM
To: Programming forum
Subject: Re: [Jprogramming] finding number
A bit more elegant solution:
g2=:((>:@:])^:([>f@:])^:_)~
A do while loop. The trick here is that the ~ adverb allows me to use two
arguments (x) and (y) when I only supply (y). The (x) can be used as a
reference and I just increment and test until f(x) > y
ts 'g2 6037'
0.106917 371328
g=: i.~ f"0@:i.@:+:
ts 'g 6037'
12.5618 869376
Cheers, bob
On 2010-12-26, at 3:38 PM, bob therriault wrote:
> Whoops, too much turkey!!
>
> I meant to say that:
> g=: i.~ f"0@:i.@:+:
> g 75
> 87
>
> Cheers, bob
>
> On 2010-12-26, at 1:48 PM, bob therriault wrote:
>
>> Hi Björn,
>>
>> This is a bit brute force but it seems to work.
>> g=: i.~ f"0@:i.@:+:
>> g 87
>> 75
>>
>> Essentially applying f to a list up to twice the argument (y) and
>> returning the index (x) of the first spot f(x)=y
>>
>> Cheers, bob
>>
>> ps. I believe your original f can also be written as:
>> f1=: [: # i. -./ 2 3 ^~ i.
>>
>> On 2010-12-26, at 11:47 AM, Björn Helgason wrote:
>>
>>> I have a small task that looks like this
>>>
>>> f=: [: # i. -. (2 ^~ i.) , 3 ^~ i.
>>> f 87
>>> 75
>>>
>>> I want to use tacit to find what number gives me 75 numbers (the
>>> answer being 87)
>>>
>>> Could be asking what argument y do I need to find x numbers
>>> according to the formula above
>>>
>>> --
>>> Björn Helgason, Verkfræðingur
>>> Fornustekkum II
>>> 781 Hornafirði,
>>> t-póst: [email protected]
>>> gsm: +3546985532
>>> sími: +3544781286
>>> http://groups.google.com/group/J-Programming
>>>
>>>
>>> Tæknikunnátta höndlar hið flókna, sköpunargáfa er meistari
>>> einfaldleikans
>>>
>>> góður kennari getur stigið á tær án þess að glansinn fari af skónum
>>> /|_ .-----------------------------------.
>>> ,' .\ / | Með léttri lund verður |
>>> ,--' _,' | Dagurinn í dag |
>>> / / | Enn betri en gærdagurinn |
>>> ( -. | `-----------------------------------'
>>> | ) | (\_ _/)
>>> (`-. '--.) (='.'=) ♖♘♗♕♔♙
>>> `. )----' (")_(") ☃☠
>>> --------------------------------------------------------------------
>>> -- 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
