Back to Forum | View unanswered posts | View active topics





Post a reply
Username:
Note:If not registered, provide any username. For more comfort, register here.
Subject:
Message body:
Enter your message here, it may contain no more than 60000 characters. 

Smilies
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:
Font size:
Font colour
Options:
BBCode is ON
[img] is ON
[flash] is OFF
[url] is ON
Smilies are ON
Disable BBCode
Disable smilies
Do not automatically parse URLs
Confirmation of post
To prevent automated posts the board requires you to enter a confirmation code. The code is displayed in the image you should see below. If you are visually impaired or cannot otherwise read this code please contact the %sBoard Administrator%s.
Confirmation code:
Enter the code exactly as it appears. All letters are case insensitive, there is no zero.
   

Topic review - Algorithm of interred
Author Message
Mirzza
  Post subject:  Algorithm of interred  Reply with quote
Hey guys, I need help finding a search algorithm that would allow me to find the lowest 7 floating-point numbers in an array. The catch is that the array is likely to be about 200 numbers long and that I need to be able to run this search very very quickly. Like on the order of over 300 times per second. Standard search algorithms dont particularly help because they seem to do tons and tons of extra work when I only need the lowest seven elements, and neither do sorting algorithms the list is going to be unsorted most of the time, so I cant simply pull off the top or bottom 7 numbers. Ive already searched through a Knuth book and tried googling it, but I dont really get any hits. Does anyone have any good ideas preferably ones that arent impossible to implement in C/C?
Post Posted: Wed Nov 16, 2011 9:03 pm
hannes
  Post subject:  Re: Algorithm of interred  Reply with quote
interred used to be a preprocessing step of the Buchberger algorithm
(it is now implemented differently).
It simply tries to reduce every lead term by alll the other polynomials
and continues then with the non-leading terms.
That is roughly n*n*m normal form computations
(n: number of polynomials, m: max. length of the polynomials).
And a normal form computation itself may be quite complex.

The result is nota Groebner bases, only a (hopefully) smaller
generating set of the ideal.
Post Posted: Wed Oct 12, 2011 1:32 pm
pu_king81
  Post subject:  Algorithm of interred  Reply with quote
Hi,

maybe a stupid question: but what is the complexity of the algorithm which interred uses? I would like to avoid the computation of a groebner basis. Can anyone help me out with information? Google did not really yield the corresponding information.

Regards,
pu
Post Posted: Thu Aug 25, 2011 7:28 pm


It is currently Fri May 13, 2022 11:07 am
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group