some simple questions (1 Viewer)

[...]

brilliant


thanks turtle!!

now i shall conquer my assignment

 

[casebash]

Analysis of two algorithms provided. Implementation is important, but I will assume the most efficent i know. For simplicity i will treat the problem as simplifying m!/n!

Prime Factorisation: All the primes less than n can be found in O(nlogn) time by a prime sieve. Given all the prime factors of a number, of which there are f<=O(log n), the factorisation can be found in O(f) <= O(log n) time = O(nlogn) for all numbers. By storing the number of factors for each prime number in an array we can update for each number in O(1) time, and count them up in O(n) time. Therefore the algorithm takes O(nlogn) time excluding time taken to multiply all the numbers back together. Note this may actually become O(nlogn logn) as the multiplication operation will increase in time as numbers get larger. Number we have to multiply is n log n each takes time as described below (see LABEL) so we get O(n logn (log(nlogn))^1.58) =O(n (log n)^2.58)



GCD: Multiplaction of a big number B, with a small number, S, takes O(log B log s) using the standard digit by digit method. B<=n! and multiply by n numbers so time is O(nlog(n!)logs)=O(n (log1+log 2+...log n)log s) now lim as n->OO log1+log2+...logn > n but less than n^c where c>1. Therefore about O(n^(2+1/OO)log s). Now s<=n so get O(n^(2+1/OO)log n).

LABEL:
It is faster if we instead multiply numbers to get numbers approimately equal sized. Karatsuba's divide-and-conquer algorithm takes d^1.58 for multiplication of two numbers with at most d digits. So we can multiply the numbers together in groups of 2. Using this, at each after step we have 1/2 the numbers but about twice the number of digits taking 2^1.58/2 time as long= 2^0.58. lim as n ->OO a(2^0.58n-1)/(0.58-1) = -1/-0.42=1/0.42. So takes 1/0.42 times the amount of time of the first step. The first step multiplies n/2 groups two numbers, with at worst log (n/2) digits. Time taken is O((log(n/2))^1.58.) As n/2 multiplications total is O(n (log(n))^1.58).

Afterwards, using Eulers algorithm we get the gcd of two numbers, the greater which is B, in O(log B) time. If B=j! as before we get O(j^(1+1/OO)) time. So a faster multiplication method is necessary for the second method the work in a reasonable amount of time. So the second method should be faster, according to my approximations.

 

[who_loves_maths]

^ hehe......

 

[Trefoil]

^ you can use my method with equal efficiency in exams where no calculators are allowed... but even more importantly, you can use my way where calculators ARE allowed too - it's a simple division of numbers. your method of counting exponents and guessing which primes are constituents, etc..., are not in-built processes in a normal calculator.

so my way's a win-win situation

Somebody sure thinks they're God's gift to maths.

 

[who_loves_maths]

^ and somebody sure wasn't born with a 'gift' for discerning light & friendly discussion as being light & friendly.

maybe you should start reading the thread from the beginning? you'll see that this was a non-serious (and superficial) discussion held in the buoyant spirit of interest. it wasn't meant to be seriously competitive and certainly not arrogant... so i apologise if you think there was any meant by my post.
but know that my apology is not for my post, it's my pity and sorry for you not being able to see the triviality of the discussion.

try not to take everything too seriously and literally.

 

[Trefoil]

I've read most of your threads. Each of them involves you hurling out all sorts of usually useless formulae and a conclusion that your method is best or that somebody else is wrong. When questioned, each time you use that lame "in the spirit of maths" excuse.

GG.

 

[ogmzergrush]

try not to take everything too seriously and literally.

hahahahahahahahahahahahahah, good one chief, remember me?

 

[ogmzergrush]

^ first of all: a correction. you obviously haven't read most of my posts, because most of them are answers to the questions and problem that ppl post up in the maths forums. only a small percentage of them is actual discussion over other ppl's solutions. so why don't you go back and re-read "most" (as you claimed) of my 400 or so posts. gl.

secondly: no one forced you to read ANY of my posts - i didn't put up a sign "Trefoil, come and read this" - and i'm confident that NONE of my posts thus far have ever been directed, or refer, to you. so if you want to stop feeling insecure about yourself, then start by minding your own business

thirdly: "in the spirit of maths" is not an excuse. if you think going around the forums only posting "yep, no question about that, you're definitely right" constitute any sort of constructive criticism then you're obviously suffering from illusions. questioning the views of others, and discussing them, is an extension of your own ability to independently think over and deconstruct problems, not to mention also broadening the scope of discussion at hand. it's a conduit for the stimulation of creativity and imagination... but then again, you wouldn't know about that.
forums exist, by their very own definition, as a medium for discussion and debate - not a brainwashing playground for turning us all into yes-men.

conclusion: Therefore, in this particular case, you are wrong.

What were you saying about taking things too seriously?

Edit: let's do the timewarp agaiiiiiiiin!

 

[who_loves_maths]

Originally Posted by Trefoil
I've read most of your threads. Each of them involves you hurling out all sorts of usually useless formulae and a conclusion that your method is best or that somebody else is wrong. When questioned, each time you use that lame "in the spirit of maths" excuse.

GG.

^ first of all: a correction. you obviously haven't read most of my posts, because most of them are answers to the questions and problem that ppl post up in the maths forums. only a small percentage of them is actual discussion over other ppl's solutions. so why don't you go back and re-read "most" (as you claimed) of my 400 or so posts. gl.

secondly: no one forced you to read ANY of my posts - i didn't put up a sign "Trefoil, come and read this" - and i'm confident that NONE of my posts thus far have ever been directed, or refer, to you. so if you want to stop feeling insecure about yourself, then start by minding your own business

thirdly: "in the spirit of maths" is not an excuse. if you think going around the forums only posting "yep, no question about that, you're definitely right" constitute any sort of constructive criticism then you're obviously suffering from illusions. questioning the views of others, and discussing them, is an extension of your own ability to independently think over and deconstruct problems, not to mention also broadening the scope of discussion at hand. it's a conduit for the stimulation of creativity and imagination... but then again, you wouldn't know about that.
forums exist, by their very own definition, as a medium for discussion and debate - not a brainwashing playground for turning us all into yes-men.

conclusion: Therefore, in this particular case, you are wrong.

 

[FadeToBlack]

I haven't read ANY of your previous posts, but can tell from your previous one, you're a tool.

conclusion: I'm not wrong.

 

[Templar]

I've read most of your threads. Each of them involves you hurling out all sorts of usually useless formulae and a conclusion that your method is best or that somebody else is wrong. When questioned, each time you use that lame "in the spirit of maths" excuse.

I agree with that. To most people what's been posted sounds pretty arrogant.

 

[turtle_2468]

closed. This is getting really unproductive..