Re: Regularly populating the line - revised version

From: Gordon Sande (g.sande_at_worldnet.att.net)
Date: 01/30/05 

Date: Sun, 30 Jan 2005 21:52:27 GMT

Lord Snooty wrote:
> Thanks (for a reply somewhat snootier than my handle suggests).
> As I posted, I did hit the books before posting this, but you do raise good
> points despite your apparent reading impairment.
> (Since you impugn my academic curiosity, you will have to deal with feedback
> like this).

"On the InterNet noone knows your a dog" is the caption of one of the
standard cartoons of internet usage. Lord Snooty is as Lord Snooty does.

> I think you may also have a writing issue; (i-i) is identically zero, so your
> inequality makes no sense.
> Perhaps it is simply a typo.

Indeed a typo. Try i-1. Surely someone as accomplished as Lord Snooty
could figure out how to reverse engineer such an obvious visual trap.

> It is also a tautology that i*p/n changes. It changes for every value of i,
> irrespective whether the 'if' fires or not.
> So I have no idea what you meant by that. Another typo?

Perhaps Lord Snooty need to notice the comment "integer divide" which
means that increasing i may or may not increase i*p/n. Or perhaps Lord
Snooty need to be reminded that the default parenthesization in
mathematical notation and programming may not be the same so that the
code will read ( i * p ) / n for programming languages with an integer
divide.

Try p==3 and n==10

  3* 1/10= 3/10=0
  3* 2/10= 6/10=0
  3* 3/10= 9/10=0
  3* 4/10=12/10=1
  3* 5/10=15/10=1
  3* 6/10=18/10=1
  3* 7/10=21/10=2
  3* 8/10=24/10=2
  3* 9/10=27/10=2
  3*10/10=30/10=3

and we observe exactly three changes. Sorting out the initial and end
cases in code is left for Lord Snooty.

> However, your observation - which is correct - that a = i*p mod n may allow me
> to work up a proof.
> This is still necessary because you haven't shown that the 'if' fires exactly
> p times, which in fact is the question I posed.

The reader is expected to do some of the homework.

> It is indeed the case that the algorithm is very remisicent of Bresenham (in a
> former life I designed 3D graphics chips).
> However, this algorithm comes from a rather different domain having no
> connection with scan lines.
> The way I introduced it stands on its own; it's a populating algorithm, I
> suppose one could call it, of a completely general nature.

Think about populating some x increments with y increments. Graphics.
Diagonal line on an integer lattice. Whatever. Many different problems
lead to the same mathematics. Thus the language of science.

> LS
>
> "Gordon Sande" <g.sande@worldnet.att.net> wrote in message
> news:PR6Ld.78622$Qb.34951@edtnps89...
>
>>
>>Lord Snooty wrote:
>>
>>>Due to a typo, one more time with feeling, and less C-stylistic too:
>>>
>>>for (i=a=0; i < n; i++) {
>>> a = a + p;
>>> if (a >= n) {
>>> // fill at position i
>>> a = a - n;
>>> }
>>> // else leave position i unfilled
>>>}
>>>
>>>It's trivial to analyse this for (n mod p) = 0 of course.
>>>I'm only interested in nonzero (n mod p).
>>>
>>
>>
>>The first observation is that a is just i*p mod n.
>>Then one wants to know what make the if condition true.
>>It is true whenever the value of i*p/n (integer divide)
>>changes. Otherwise stated as (i-i)*p/n != i*p/n. This
>>starts to look like the algorithm for drawing a diagonal
>>line on an integer lattice, which is Bresenham's algorithm
>>if you are doing computer graphics. A full citation
>>is left as an exercise for the reader. Some of the dates will
>>be in the prehistoric period BG (Before Google).
>>
>>The curious handle does not suggest a strong academic interest
>>so one might even guess that the original problem is computer
>>graphics. The ancients did have considerable wisdom and the even
>>more curious habit of recording much if it in books. So the
>>obvious thing is for Lord Snooty to try reading some books.
>>
>>
>>
>>>"Lord Snooty" <bonzo@dog.com> wrote in message news:...
>>>
>>>
>>>>It's not too uncommon to want to populate n bins with a given number p of
>>>>objects, such that they are as regularly spaced as possible - we seek to
>>>>avoid
>>>>bunching, in other words. For example, if n=8 and p=2, then trivially we'd
>>>>seek one of the cyclic permutations of PxxxPxxx, where P represents one of
>>>>the
>>>>p objects and x represents an unfilled bin.
>>>>
>>>>I came across the following very efficient algorithm recently, which works
>>>>on
>>>>all tested integer pairs (n,p), n >= p. Trouble is, I have difficulty
>>>>proving
>>>>that it will always emit exactly p objects. I'd appreciate any attempts at
>>>>proving this. I'd also like to know if it has a name, because I've never
>>>>come
>>>>across it before. I can't find it in Knuth, for example, because I can't
>>>>find
>>>>a good name for it with which to do an index search. Here's the algorithm
>>>>(C-code style):
>>>>
>>>>for (i=a=0; i < n; i++) {
>>>> a += p;
>>>> if (a >= n) {
>>>> // fill at position i
>>>> a -= nN;
>>>> }
>>>> // else leave bin unfilled
>>>>}
>>>>
>>>>
>>>
>>>
>

Relevant Pages

  • Re: Regularly populating the line - revised version
    ... which is Bresenham's algorithm ... obvious thing is for Lord Snooty to try reading some books. ... >>p objects and x represents an unfilled bin. ...
    (sci.math.num-analysis)
  • Re: Regularly populating the line - revised version
    ... As I posted, I did hit the books before posting this, but you do raise good ... former life I designed 3D graphics chips). ... this algorithm comes from a rather different domain having no ... > more curious habit of recording much if it in books. ...
    (sci.math.num-analysis)