?

Log in

No account? Create an account
binary chop - oldbloke's mutterings
July 6th, 2011
01:50 pm
[User Picture]

[Link]

Previous Entry Share Next Entry
binary chop
After reading J his stories, I lie down with him for 3 minutes before leaving him to (hopefully) go to sleep. This is quiet time (in theory) so there's nothing to do, plus I have to time the 3 minutes. So, often, I count to 180. For variety, I vary how I do this. One obvious option is the binary chop - count halfway, then half of what's left, and so on.
What to do when you have to chop an odd number? With a small boy not being as quiet as one hopes, and having to keep the count, it's taken me until last night to work out the algorithm that lets you do it with only a single flag in addition to the count. I expect this is already widely known to computer scientists, but here it is for everybody else:

[count,flag]->[div((count+flag),2),mod((count+flag),2)]

180,0 - 90,0 - 45,0 - 22,1 - 11,1 - 6,0 - 3,0 - 1,1 - 1,0 - 0,1
It always ends with 0,1 so that's your termination condition

I imagine you can change the 2 to other integers and still have it work. I might try it tomorrow.

(7 comments | Leave a comment)

Comments
 
[User Picture]
From:bellinghman
Date:July 6th, 2011 03:55 pm (UTC)
(Link)
Hmm, interesting. Of course, that flag is the first binary place.

With other numbers, you might be counting a lot less of the time, or a lot more. The feature of the sequence you use is that the series 1/2 + 1/4 + 1/8 converges to 1. 1/3 + 1/9 + 1/27 ... converges a lot less (to 0.5 I think), and 2/3 + 4/9 + 8/27 ... has gone over 1 before you've finished with the second term
[User Picture]
From:oldbloke
Date:July 6th, 2011 07:04 pm (UTC)
(Link)
Um, just replacing the 2 with some other integer isn't enough, I realise - you'd have to use f((N-1)*count+flag,N), I think. Otherwise you cut the reduction faster than you reduce the rump. and that's too hard to do while attempting to convince a small boy to go to sleep. With N=2 you get a nice easy formula.
[User Picture]
From:oldbloke
Date:July 7th, 2011 08:38 am (UTC)
(Link)
"that flag is the first binary place"
So there'd be a very efficient way of doing it in assembler, though it might be hard to get at in a high-level language.
[User Picture]
From:vinaigrettegirl
Date:July 7th, 2011 07:18 am (UTC)
(Link)
OK, it is well established that I know my own ignorance.

Please, I'd honestly like to know, to what real-life situation would you apply this process and how would it /work/?
[User Picture]
From:oldbloke
Date:July 7th, 2011 08:37 am (UTC)
(Link)
Well, as I say, I use it to alleviate the tedium of counting out 3 minutes at The Boy's bedtime. But there are plenty of RealLife situations where a computer has to progressively narrow a search range where it might come in handy.
[User Picture]
From:vinaigrettegirl
Date:July 7th, 2011 09:30 am (UTC)
(Link)
I 'get' the tedium-alleviation.

Anything other than computing?

It's probably not possible for you to grasp the detail of what I don't see about exactly how this would be applied because you can plug this into RL without actually thinking about it - you stopped needing to think about how the mechanics of the process related to RL when you were probably ... twelve?

sigh
[User Picture]
From:oldbloke
Date:July 7th, 2011 09:50 am (UTC)
(Link)
I think when not using a computer the efficiency loss in handling these sorts of counts some other way (using more, or different, variables to keep track of where you are) would be insignificant; and other methods might be more transparent to a human and require less calculation.
Even when a computer is binary-chopping huge lists, it's usually searching for something, so the main concern is "which half do we look in next?" rather than efficiently doing the chop. You'd have to be really tight on memory usage to need to keep it down to 1 number plus a flag.
So quite likely there are no practical applications, apart from amusing myself. Unless anybody knows better?

Edited at 2011-07-07 09:52 am (UTC)
My Website Powered by LiveJournal.com