|
“I think the bubble sort would be the wrong way to go.” 
|
|
|
|
|
Maybe yes maybe no. The question is not about sorting but about searching the sorted table, though.
|
|
|
|
|
Oh good grief... did none of you CP geeks get the reference[^] ? 
|
|
|
|
|
I don't think I understand the your requirements correctly, because to me it looks like any key <= x will be fine, and since the table is sorted, you could just take the first one and return an error if it is > x
|
|
|
|
|
Hi,
liquid_ wrote: I wonder whether there is a more compact algorithm or maybe more efficient
As you use size_t you are probably using a C++ compiler here.
Then if Key is any type with operator<(const Key& other) defined:
#include <algorithm>
std::min_element( base, base + nElts );
returns a const Key* pointing to the smallest key in the array.
cheers,
AR
When the wise (person) points at the moon the fool looks at the finger (Chinese proverb)
|
|
|
|
|
Thanks for constructive reply.
Firstly, I used size_t only for shortage of unsigned int. The rest of code is written in pure C and it should be just such - a more universal one.
Secondly, analyzing the std::min_element function it is clear that it has linear complexity. What I tried to aim is logarithmic complexity.
However, comparing my implementation of
lbound(const void* key, void *base, unsigned int nmemb, unsigned int size, int (*compare)(const void *e1, const void *e2)) with bsearch implementation, it seemed to me that my lbound is not so compact and efficient as bsearch standard implementation (two additional checks - size==0 and size==1, and one more comparison after size==1 check).
Maybe its the matter of lower bound specific. bsearch just returns NULL if it does not find a key, lbound returns NULL only if key is lower than first element of table.
Regards
|
|
|
|
|
Hi,
liquid_ wrote: code is written in pure C and it should be just such - a more universal one.
This is really planet-dependant
liquid_ wrote: What I tried to aim is logarithmic complexity.
If your data are unsorted you will have to check each and any for smaller than current minimum, so you will never get under linear complexity. If your data are sorted the problem is trivial.
More generally you should think that more man*hours have been spent on each part of the Standard C++ Library than you can provide in your total professional life.
Good luck,
AR
When the wise (person) points at the moon the fool looks at the finger (Chinese proverb)
|
|
|
|
|
The assumption is that data are sorted. I'd just like to know if I found this trivial solution.
Concerning the philosophy of using ready made STL or creating own solutions, it depends on particular needs. Many programs are written in C not in C++ because of various reasons (eg. UNIX or LINUX areas). I use pure C or C++ with STL or other available libraries (eg. BOOST, MFC, .NET aso) as well. Most of software I do is made just for fun or to search/find interesting solutions, or to resolve some problems I meet in my job. It is not my core business.
Anyway, thanks for your points.
Regards
|
|
|
|
|
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind!
The square of any prime number >= 5 can be expressed as 1 + a multiple of 24
or
If p is prime, then p ^ 2 = 1 + 24 * n, for some n
Don't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!)
[edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)
modified on Thursday, November 4, 2010 6:37 AM
|
|
|
|
|
what is that "n" it is 1 for p = 5??
|
|
|
|
|
Yes, for
p=5, n=1
p=7, n=2
p=11, n=5
p=13, n=7
If you can work out a forumla that spits out each value of n that produces the "next" prime, you'll be able to retire early
|
|
|
|
|
Try
p ^ 2 = 1 + 24 * (p - 6)
Just say 'NO' to evaluated arguments for diadic functions! Ash
|
|
|
|
|
OK...
p^2 - 24*p + 143 = 0
So..?
|
|
|
|
|
Just say 'NO' to evaluated arguments for diadic functions! Ash
|
|
|
|
|
Me too - ome of us is being a bit dumb here (most likely me...)
I just re-wrote the equation you posted... what does it prove? Is there a typo in it (yours)?
|
|
|
|
|
No typo as far as I am aware. I just thought you wanted to know what was the value of 'n' in your original question.
Just say 'NO' to evaluated arguments for diadic functions! Ash
|
|
|
|
|
Ah, got you - except that it doesn't work for all values of p
p=5, n=1 != p-6
p=7, n=2 != p-6
p=11, n=5 ok
p=13, n=7 ok
p=17, n=12 != p-6
...
|
|
|
|
|
a quadratic equation like that has at most two solutions, so it is hardly a way to discover lots of primes.
|
|
|
|
|
We have a saying round here: "Don't tell I, tell 'e"... especially as that particular one doesn't even have any (real) solutions at all!
|
|
|
|
|
you'll have more luck with
x<sup>2</sup> + x + 41
for natural values of x.
|
|
|
|
|
Now you're just confusing me....
|
|
|
|
|
actually that's not correct; when p=7 then by your formula we would have 49=1+24*1 = 25
|
|
|
|
|
that is correct, even when n needs to be 1/8 for p=2.
|
|
|
|
|
Actually, that's QI.. it also "works" for p=3 (n=1/3) - so in fact, the *only* value of p for which n is neither an integer nor a proper fraction is 4.[edit] OOPS what an idiot! since when was 4 a prime! 
|
|
|
|
|
Well, I know you are not asking for a mathematical proof, but like I am much better at maths than metaphisics...
Where does 24 come from?
Since p is prime and greater than 5, p cannot be an even number. So:
p2-1=(p-1)*(p+1).
Like p is odd, both (p-1) and (p+1) are even, so we can say:
p2-1=2a*2b=4ab.
Like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 4, so 2a is multiple of 4 or 2b is multiple of 4, so we can express this like:
p2-1=4a*2c=8ac
or
p2-1=4b*2d=8bd
I will examine just one of these two cases becouse they are symmetrical. Now, like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 3, so:
p2-1=8a*3d=24ad
or
p2-1=8c*3e=24ce
And there it is.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
