Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm studying Tomas Cormen Algorithms book and solve tasks listed after each chapter.

I'm curious about task 1-1. that is right after Chapter #1.

The question is: what is the best way to solve: $n\lg(n) \le 10^6$, $n \in \mathbb Z$, $\lg(n) = \log_2(n)$; ?

The simplest but longest one is substitution. Are there some elegant ways to solve this? Thank you!

Some explanations: $n$ - is what I should calculate - total quantity of input elements, $10^6$ - time in microseconds - total algorithm running time. I should figure out nmax.

share|improve this question
2  
Try WA, click Approximate form –  Ilya May 30 '13 at 13:17
1  
Quick eyeball $\log_2(n) << \sqrt{n}$ and $n \sqrt{n} = n^{3/2} \leq 10^6 = (10^4)^{3/2}$ so you need roughly $n >> 10^4$. –  gt6989b May 30 '13 at 13:18
    
@gt6989b Thank you very much for tolerance and editing. I will edit correctly further questions myself. –  DaddyM May 30 '13 at 16:00
    
Please do not post the same question on multiple Stack Exchange sites. If you really want the math perspective and the CS perspective, tailor the question to each site, and at least have the decency to link the questions to each other. –  Gilles May 30 '13 at 23:31
    
@Gilles no problem. This case is unusual for me. This thread was raised on CS site first. But they downvoted my question without any explanation and without providing me with any answers. I posted this question at this wonderful site and got fantastic community feedback. Again I'm very glad to join this opened and friendly community. Greetings to all! –  DaddyM May 31 '13 at 5:15

6 Answers 6

The first approximation for the inverse of $x\;\text{lg}\; x$ is $x/\text{lg}\; x$. So begin with the value $10^6/\text{lg}(10^6)$, then adjust by substitution/bisecion.

share|improve this answer
    
Yes, this is a quicker way to jumpstart the bisection in my answer than the $2^p\cdot p$ search. –  Michael Grant May 30 '13 at 16:39

First, I found a power of 2, $n=2^p$, such that $n\log_2 n=2^p\cdot p\approx 10^6$. Since $2^{20}\approx 10^6$, it's probably going to be a click or two below that. Sure enough, $16\cdot 2^{16}=2^{20}=1048576$.

Now I figured that $\log_2 n \approx 16$, so $n \approx 10^6/16=62500$. Sure enough, for that $n$, $n\log_2 n \approx 995723$.

Now some simple searching or bisection will do the trick: $63000$ and $62750$ are too large; $62625$, $62700$, $62725$ are too small; etc. The number of bisection steps, if you use strict halving of the interval, is bounded by $\log_2 n$. So you know you'll get there quickly. Eventually I found that if $n=62746$, $n\cdot\log_2 n \approx 999998$.

That is the largest possible integer $n$; so $n\leq 62746$ is your answer.

EDIT: earlier I suggested that Newton's method was too beefy for the job. Well, I think I'm wrong. After all, the derivative of $f(n)=n\log_2 n$ is just $f'(n)=\log_2 n+\log_2 e$, and you have to compute $\log_2(n)$ anyway every time you do a bisection step. So the derivative information is there, free to use. If I were coding up an algorithm, yes I think I would do Newton's method. A similar case could be made for using Newton's even for the initial $p\cdot 2^p$ search.

share|improve this answer

For my money, the best way is to solve $n\log_2n=10^6$ by Newton's Method.

share|improve this answer
1  
If we start with $x_0 = 10^6$ as an obvious overestimate, then Newton iterates are $x_1 = 114282.07$, $x_2 = 63846.44$, $x_3 = 62746.92$, and $x_4 = 62746.13$. So the number of Newton iterates needed is about half the number of fixed-point iterates to reach the integer part of the root. Even assuming the tighter bracket proposed by @MichaelC.Grant for bisection, a dozen steps are needed to pin down the integer part. –  hardmath May 31 '13 at 15:13

If something cheesier than Newton's method is wanted, I recommend the fixed point iteration:

x := (10^6)/log_2(x) 

This is easily done with a calculator applet by storing constant (10^6) * log_10(2) and thereafter taking $\log_{10}(x)$, reciprocating, and then multiplying by the recalled constant.

Starting with obvious overestimate $x_0 = 10^6$, the fixed-point iterates alternate between under- and over-shooting:

x1 = 50,171.67
x2 = 64,042.69
x3 = 62,630.17
x4 = 62,756.63
x5 = 62,745.18
x6 = 62,746.21
x7 = 62,746.12

Thus the largest possible integer is $n = 62746$, as Michael already stated.

share|improve this answer

To solve for $n\log_2(n)=10^6$, we can use the Lambert-W function. A bit of manipulation yields $$ \log(n)e^{\log(n)}=10^6\log(2) $$ and the Lambert-W function, being the inverse of $xe^x$, says that $$ \log(n)=\mathrm{W}\left(10^6\log(2)\right) $$ or $$ n=\exp\left(\mathrm{W}\left(10^6\log(2)\right)\right) $$ on the positive reals, the Lambert-W function is monotonically increasing, so you can simply get the desired inequality.

Mathematica gives the result $62746.1264697$ for N[Exp[LambertW[10^6Log[2]]],12].

Therefore, the largest $n$ is $62746$.

share|improve this answer

I think Newton's Method and Fixed-Point Iteration are too complicated when you're looking for an integer. A simple Binary Search would be much more effective, and probably faster if you don't need as many floating-point operations.

I give more details on my answer on this question's duplicate on CS.SE.

share|improve this answer
1  
I see that the problem can be rewritten as an integer-only one, $n^n \le 2^{10^6}$, but a naive implementation of this would tranfer work with ordinary floating point operands into work with big integers. Looking at your CS.SE post it seems you have in mind the function evaluation per bisection step, which involves taking a floating-point(?) logarithm base 2 of $x$ and multiplying the result by $x$. Even exercising some cleverness, e.g. to restrict this to integer parts $x$, it isn't clear how to save on floating-point operations. –  hardmath May 31 '13 at 15:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.