Forums > MaxMSP

### lowest common divider

May 02 2007 | 11:46 pm

Hi all,

Sorry, this is probably very basic for most of you but – is there an object to find the lowest common divider of a single number other than 1.

Went thru max reference and couldn’t find anything – checked out Mathworld too but… that just confused me further.

thanks
vic

May 03 2007 | 12:15 am

Quote: pechnatunk wrote on Wed, 02 May 2007 16:46
—————————————————-
> Hi all,
>
> Sorry, this is probably very basic for most of you but – is there an object to find the lowest common divider of a single number other than 1.
>
> Went thru max reference and couldn’t find anything – checked out Mathworld too but… that just confused me further.
>
> thanks
> vic
—————————————————-

Huh? Could you use a different term. Common usually implies more than one number. Are you looking for factors, or…?

mz

May 03 2007 | 2:05 am

sorry,

yes, now that i think about it I want the lowest factor –

8 = 2 9 = 3 10 = 5 7 = 1 etc.

i’m using this as a basis for sample slicing – where i’ll have a list of selected dividers in a coll similar to time signiture. these get multiplied by the length – but i want to constrain the the resolution of the length to a factor of the divider – using the lowest factor and the modulus of it – where each mod zero is an allowed length value. start position of the sample will use a similar technique.

I’ve built it to random/drunk these parameters but i’d like to quantise it to a signiture using this technique.

hope that makes it clearer.

May 03 2007 | 6:30 am

here is something. seems to cause stack overflow with some high numbers so i limited it to integers less than 1024.

max v2;
#N vpatcher 304 108 898 548;
#P window setfont "Sans Serif" 9.;
#P window linecount 1;
#P newex 200 250 27 196617 i;
#P window setfont "Sans Serif" 20.;
#P number 316 334 66 20 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P window setfont "Sans Serif" 9.;
#P newex 200 190 31 196617 t b 1;
#P newex 316 273 27 196617 i;
#P comment 35 121 63 196617 bang to test;
#P button 100 102 32 0;
#P comment 317 369 71 196617 lowest factor;
#P message 359 165 14 196617 1;
#P newex 267 196 40 196617 t b b 0;
#P newex 267 165 32 196617 sel 0;
#P newex 307 249 29 196617 gate;
#P window setfont "Sans Serif" 20.;
#P number 231 334 66 20 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P window setfont "Sans Serif" 9.;
#P newex 231 250 27 196617 1;
#P number 353 219 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P message 381 161 14 196617 2;
#P button 334 165 15 0;
#N counter;
#X flags 0 0;
#P newobj 353 196 66 196617 counter;
#P number 267 138 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P newex 267 113 27 196617 %;
#P newex 226 165 32 196617 sel 1;
#P newex 259 72 73 196617 t b b b i;
#P number 226 138 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P number 259 50 52 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P number 134 58 35 9 3 1024 3 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P newex 226 112 27 196617 /;
#P comment 223 369 79 196617 greatest factor;
#P comment 40 59 97 196617 load number to test;
#P fasten 7 0 24 0 231 186 205 186;
#P connect 24 0 26 0;
#P fasten 3 0 26 1 139 217 222 217;
#P fasten 3 0 2 0 139 92 231 92;
#P fasten 6 2 2 0 306 102 231 102;
#P connect 2 0 5 0;
#P connect 5 0 7 0;
#P fasten 18 0 14 0 272 232 236 232;
#P fasten 19 0 14 0 364 190 236 190;
#P fasten 26 0 15 0 205 300 236 300;
#P connect 14 0 15 0;
#P fasten 6 3 2 1 327 99 248 99;
#P connect 7 1 14 1;
#P fasten 16 0 4 0 312 304 176 304 176 40 264 40;
#P connect 4 0 6 0;
#P fasten 3 0 8 0 139 107 272 107;
#P fasten 6 1 8 0 285 96 272 96;
#P connect 8 0 9 0;
#P connect 9 0 17 0;
#P connect 24 0 18 0;
#P connect 17 0 18 0;
#P fasten 6 3 8 1 327 105 289 105;
#P fasten 18 2 16 0 302 231 312 231;
#P fasten 19 0 16 0 364 193 312 193;
#P fasten 18 0 23 0 272 270 321 270;
#P connect 23 0 25 0;
#P fasten 13 0 16 1 358 240 331 240;
#P fasten 24 1 23 1 226 242 338 242;
#P connect 16 0 23 1;
#P fasten 21 0 11 0 105 158 339 158;
#P fasten 6 0 11 0 264 132 339 132;
#P fasten 11 0 10 0 339 187 358 187;
#P connect 10 0 13 0;
#P fasten 21 0 19 0 105 158 364 158;
#P fasten 21 0 12 0 105 154 386 154;
#P connect 12 0 10 2;
#P pop;

May 03 2007 | 9:38 am

"8 = 2 9 = 3 10 = 5 7 = 1 etc."

10 => 2 you must mean?

Anyway, fun question. Here’s a patch for just the lowest factor other than 1:

#P window setfont "Sans Serif" 9.;
#P window linecount 1;
#P newex 67 125 47 196617 t b i;
#P newex 67 151 27 196617 i;
#P newex 67 244 50 196617 print end;
#P newex 67 223 27 196617 i;
#P newex 67 196 32 196617 sel 0;
#P newex 67 174 27 196617 %;
#P newex 67 74 107 196617 t b 2 i 1;
#N counter 2 100;
#X flags 0 0;
#P newobj 67 101 74 196617 counter 2 100;
#P number 67 45 35 9 3 1024 3 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P connect 2 2 7 1;
#P connect 2 2 1 4;
#P connect 2 1 1 2;
#P fasten 8 1 5 1 109 217 89 217;
#P fasten 8 1 3 1 109 170 89 170;
#P connect 5 0 6 0;
#P connect 4 0 5 0;
#P connect 3 0 4 0;
#P connect 7 0 3 0;
#P connect 8 0 7 0;
#P connect 1 0 8 0;
#P connect 2 0 1 0;
#P connect 4 1 1 0;
#P connect 0 0 2 0;
#P window clipboard copycount 9;

It too seems to produce stack overflows when putting in larger primes. Comes from using counter too heavily, i presume. The patch below shows that it’s helpful to even have one % in the loop; the right one overflows sooner than the left one. What would be a good workaround?

#P window setfont "Sans Serif" 9.;
#P number 500 140 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P window linecount 1;
#P newex 149 115 72 196617 loadmess 500;
#P number 268 161 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P newex 268 63 30 196617 t b b;
#P button 268 45 15 0;
#P newex 340 208 55 196617 print done;
#P newex 340 161 170 196617 if \$i1 == \$i2 then \$i1 else out2 \$i1;
#P message 288 85 33 196617 set 1;
#N counter 0 0 2000;
#X flags 0 0;
#P newobj 268 110 89 196617 counter 0 0 2000;
#B color 5;
#P number 41 161 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P number 149 142 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P newex 41 63 30 196617 t b b;
#P button 41 45 15 0;
#P newex 113 208 55 196617 print done;
#P newex 113 186 32 196617 sel 0;
#P newex 113 161 46 196617 % 1000;
#P message 61 85 33 196617 set 1;
#N counter 0 0 2000;
#X flags 0 0;
#P newobj 41 110 89 196617 counter 0 0 2000;
#B color 5;
#P connect 16 0 7 0;
#P fasten 16 0 17 0 154 136 505 136;
#P connect 17 0 11 1;
#P connect 5 0 6 0;
#P connect 3 1 0 0;
#P fasten 1 0 0 0 66 105 46 105;
#P connect 6 0 0 0;
#P connect 0 0 8 0;
#P connect 6 1 1 0;
#P connect 0 0 2 0;
#P connect 2 0 3 0;
#P connect 3 0 4 0;
#P connect 7 0 2 1;
#P connect 13 0 14 0;
#P connect 11 1 9 0;
#P connect 14 0 9 0;
#P fasten 10 0 9 0 293 105 273 105;
#P connect 9 0 15 0;
#P connect 14 1 10 0;
#P connect 9 0 11 0;
#P connect 11 0 12 0;
#P window clipboard copycount 18;

A patch to get the lowest common denominator off a list of unknown length sounds good too, maybe some other time…

May 03 2007 | 10:09 pm

not that i would know it offhand now … but there
is some very funny trick how to check this with
simple algebra, isnt it?
maybe someone knows what i mean ..

May 03 2007 | 10:26 pm

That’s what the deferlow object is for! Always always insert deferlow in your loop back– in this case, the right outlet of "select 0" would connect to a deferlow, and that connects back to the counter. I’m by no means a programming expert, I just stumbled upon this. Deferlow, I guess, is like a ‘Yield’ sign for Max, letting the system do required maintenance while your patch is running. (Wow, I actually had a fresh bit of useful info for the Max list!)

May 03 2007 | 10:27 pm

Quote: pechnatunk wrote on Thu, 03 May 2007 04:05
—————————————————-
> yes, now that i think about it I want the lowest factor –
>
> 8 = 2 9 = 3 10 = 5 7 = 1 etc.
—————————————————-

You want to single out the lowest prime factor.

There is a prime number generator in Tap.Tools that might help.

Also, the Sieve of Erastosthenes is the traditional efficient method for finding primes. Googling on the term should give you some ideas. (Sorry, I haven’t looked at patches submitted in detail, but the stack overflows leave me thinking they’re not Erastosthenes).

Hope this helps,
P.

May 04 2007 | 6:24 pm

David Wright schrieb:
> That’s what the deferlow object is for! Always always insert deferlow
> in your loop back– in this case, the right outlet of "select 0"
> would connect to a deferlow, and that connects back to the counter.
> I’m by no means a programming expert, I just stumbled upon this.
> Deferlow, I guess, is like a ‘Yield’ sign for Max, letting the system
> do required maintenance while your patch is running. (Wow, I actually
> had a fresh bit of useful info for the Max list!)

Yes, and no, in the patch which would overflow the stack on big numbers,
it might be fine if you can guarantee that the number stays low.
deferlow is slowing down things by using the scheduler queue instead of
the stack.
In the patch I posted recently for finding the occurance of more than
the half of its elements being in a certain range, there is recursion
(which means feedback) but no deferlow. And its not needed, because the
condition to break the recursion has a max of 256 steps (in theory, and
only because of the limitation of zl). That’s not dangerous. Also as the
calculation doesn’t put out anything before the result is found, the
stack size needed is not too high.

One thing to look at if a stack overflow only happens with big numbers
is, optimization. You might not need the feedback for all cases etc,
Sometimes you can just "turn around" the calculation instead of starting
with low numbers going up, you could go down from high numbers…

Peters quote is correct I guess:
Peter Castine schrieb:
> (Sorry, I haven’t looked at patches submitted in detail, but the
> stack overflows leave me thinking they’re not Erastosthenes).

If you do not need the calculation fast, a deferlow might be fine
though… (In this case Erastosthenes is better… ;-)

Stefan

Stefan Tiedje————x——-
–_____———–|————–
–(_|_ —-|—–|—–()——-
— _|_)—-|—–()————–
———-()——–www.ccmix.com

May 05 2007 | 4:57 am

Thanks for that info, Stefan… I made 3 mistakes, writing the word "always," writing the word "always" again, and pretending I really knew what I was talking about…

Stefan wrote:
> Sometimes you can just "turn around" the calculation instead of
> starting with low numbers going up, you could go down from high
> numbers…

Yes, I noticed recently that works.

"You can’t go back. The answer is No. And wishing for it only makes it bleed." — Tom Waits

May 05 2007 | 8:38 am

Quote: Bas van der Graaff wrote on Thu, 03 May 2007 19:38
—————————————————-

> 10 => 2 you must mean?

Sort of,

Peter you’re right I need to find the prime factors and then be able to switch between them eg. if divided into 24 it may be useful to use either 2 or 3 etc. thats why I said 10 = 5 – i was thinking of a sample in 5/4.

Anyway thanks for all the help – for various reasons I was only able to open the patch from robtherich but I had a look at Erastosthenes and it makes sense but will take a while – I have very limited math syntax knowledge, and recursion in Max is something I’m yet to grasp.

May 08 2007 | 3:46 am

OK – I’m gonna try this without recursion.

But first …

I need to construct a list of n values which is consecutive numbers from 1 -> n.

after that i should be able to solve this – but will probably be quite clunky.

May 13 2007 | 11:11 am

sorry, should have specified that previous post was a question

does anyone know how to construct a list of consecutive numbers.

to the value n.

it would be very easy in Scheme – but Max… ?

May 13 2007 | 11:45 am

May 13 2007 | 6:10 pm

On 13 mai 07, at 13:45, jose manuel berenguer wrote:

> for shure, you will find a better and shorter way to do it, but
> here is a possibility

zl group?

ej

#P window setfont "Sans Serif" 9.;
#P user textedit 416 203 612 240 32896 3 9 1;
#P window linecount 1;
#P newex 416 176 62 196617 prepend set;
#P newex 386 76 76 196617 t i i;
#P number 386 59 35 9 0 0 64 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P newex 386 97 40 196617 uzi;
#P newex 416 132 46 196617 zl group;
#P connect 2 0 3 0;
#P connect 3 0 1 0;
#P connect 3 1 0 1;
#P connect 0 0 4 0;
#P connect 1 2 0 0;
#P connect 4 0 5 0;
#P window clipboard copycount 6;

May 13 2007 | 6:44 pm

May 13 2007 | 7:14 pm

i don’t really use javascript in max that much, so i’m not familiar
with it’s drawbacks… but couldn’t this whole lowest common factor
thing be solved very simply with a js patch like the one below?

function msg_int (x) {
var i=0;
var quotient;
var divisor = 0;
for (i =2; i < = Math.floor(x/2); i++) {
quotient = x/i;
if (quotient == Math.floor(quotient)) {
divisor = i;
break;
}
}
if (divisor > 0) {
outlet(0,divisor);
} else {
outlet(0,1);
}
}

On 5/13/07, Emmanuel Jourdan wrote:
> On 13 mai 07, at 13:45, jose manuel berenguer wrote:
>
> > for shure, you will find a better and shorter way to do it, but
> > here is a possibility
>
> zl group?
>
> ej
>
>
> #P window setfont "Sans Serif" 9.;
> #P user textedit 416 203 612 240 32896 3 9 1;
> #P window linecount 1;
> #P newex 416 176 62 196617 prepend set;
> #P newex 386 76 76 196617 t i i;
> #P number 386 59 35 9 0 0 64 3 0 0 0 221 221 221 222 222 222 0 0 0;
> #P newex 386 97 40 196617 uzi;
> #P newex 416 132 46 196617 zl group;
> #P connect 2 0 3 0;
> #P connect 3 0 1 0;
> #P connect 3 1 0 1;
> #P connect 0 0 4 0;
> #P connect 1 2 0 0;
> #P connect 4 0 5 0;
> #P window clipboard copycount 6;
>

May 13 2007 | 11:02 pm

Quote: mcartwright@gmail.com wrote on Mon, 14 May 2007 05:14
—————————————————-
> i don’t really use javascript in max that much, so i’m not familiar
> with it’s drawbacks… but couldn’t this whole lowest common factor
> thing be solved very simply with a js patch like the one below?
>
> function msg_int (x) {
> var i=0;
> var quotient;
> var divisor = 0;
> for (i =2; i < = Math.floor(x/2); i++) {
> quotient = x/i;
> if (quotient == Math.floor(quotient)) {
> divisor = i;
> break;
> }
> }
> if (divisor > 0) {
> outlet(0,divisor);
> } else {
> outlet(0,1);
> }
> }

Cool thanks,

seems like I should take a look at java script.
however – the reason I asked about constructing a list of consecutive numbers is because I realised I not only wanted to find the lowest factor but all prime factors – this would allow a changable resolution in quantisation.
But it looks like making a java object to do this is the neatest technique – especially since I didn’t want my divider limited to 256 – which is what happens with the above two solutions – due to the limitations of Max message and text boxes, but of course thanks anyway.

Mar 10 2009 | 5:03 am

OK I’m re-opening this can of worms.

I left this problem ages ago and have recently gone back to it.

I’d like to get a list of say, the lowest 3-5 prime factors of a number.
I’ve tried using the explaination of the Sieve of Eratosthenes algorithm on wikipedia

But I’m approaching 2 brick walls – I’d like to use it with numbers above 256 (entry limit on message and text boxes)

also – I’m having trouble recursively truncating the list and applying the maths.

Thanks heaps to Jose and Emmanuel for the list generating patches.

And thanks mcartwright – but I can’t adapt your java script for the life of me.

So yeah – It would be great to be able to get the lowest 3 – 5 prime factors of an integer instead of only the lowest.

thanks.

Mar 10 2009 | 10:42 am

This js will give you all the prime factors.
Just getting the first few can be done using [zl thin] and [zl slice].

function msg_int(v)
{
while (v%2==0)
{
outlet(0,2);
v/=2;
}
var i=3;
while (i*i1) outlet(0,v);
}

And a patch, save the js as primes.js

— Pasted Max Patch, click to expand. —

Edit: tabs are not stored?

Mar 10 2009 | 10:57 pm

Beautiful!!
It works a charm.
Thanks.

Viewing 21 posts - 1 through 21 (of 21 total)

Forums > MaxMSP