lowest common divider
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
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
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.
here is something. seems to cause stack overflow with some high numbers so i limited it to integers less than 1024.
"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:
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?
A patch to get the lowest common denominator off a list of unknown length sounds good too, maybe some other time...
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 ..
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!)
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.
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
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
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.
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.
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... ?
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
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
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;
>
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
> 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.
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.
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*i
{
if (v%i==0)
{
v/=i;
outlet(0,i);
}
else i+=2;
}
if (v>1) outlet(0,v);
}
And a patch, save the js as primes.js
Edit: tabs are not stored?
Beautiful!!
It works a charm.
Thanks.