| Author |
Message |
|
simonzack
Advanced Newbie
Joined: 25 Dec 2007
Posts: 71
|
 Posted: 04 Apr 2008 01:54:46 am Post subject: |
|
|
I tried to search for the code for Berlekamp's algorithm for ages, but can't any, can somebody give me some code for this factorizing algorithm?
(On wikipedia, it dealts with ring theories and things, but I don't want to look for it all just for this algorithm to implement)
(even pseudo code)
thanks! |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 04 Apr 2008 08:34:29 am Post subject: |
|
|
| If you're looking for a way to factor numbers, Berlekamp's algorithm is not what you're looking for. I mean, it deals with "ring theories and things" because it's an algorithm for factoring polynomials over finite fields, and I can't see a use for that if you don't know anything about ring theory in the first place. |
|
| Back to top |
|
|
luby
I want to go back to Philmont!!
Calc Guru
Joined: 23 Apr 2006
Posts: 1477
|
| Posted: 05 Apr 2008 07:45:43 am Post subject: |
|
|
| Are you just looking for a factoring algorithm? |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 05 Apr 2008 11:24:01 am Post subject: |
|
|
The only nontrivial factoring algorithm I know that might be useful by itself on the TI-83+ is the quadratic sieve. Even that might be fairly complicated to implement, but easier than more advanced methods.
Wikipedia claims the quadratic sieve is fastest for factoring numbers with less than 100 digits. You'd need to write several big-integer routines to even deal with numbers larger than that, so this is definitely good enough for all normal numbers.
Even the quadratic sieve might be overkill, though. I'm not sure how it compares to the obvious factoring approach (divide by odd numbers less than root n) for the relatively small numbers you'd be dealing with. |
|
| Back to top |
|
|
simonzack
Advanced Newbie
Joined: 25 Dec 2007
Posts: 71
|
| Posted: 06 Apr 2008 12:36:53 am Post subject: |
|
|
| no, I'm really looking for a polynomial factoring algorithm, I need to implement it, is it complicated in code, and are there any C code implementations I can check? |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 06 Apr 2008 08:10:39 am Post subject: |
|
|
And are you sure you're trying to factor polynomials over finite fields? That seems to me like a fairly unpopular application.
Factoring polynomials is equivalent to finding roots. |
|
| Back to top |
|
|
simonzack
Advanced Newbie
Joined: 25 Dec 2007
Posts: 71
|
| Posted: 06 Apr 2008 08:20:30 pm Post subject: |
|
|
| Yeah, it's needed in a function to see where user-defined arrays overlap (polynomials), and they could be anything, (like array1[2n] && array2[3n]), the maximum values of the index, the program needs this function... anyway, you're right, my program is unpopular |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 07 Apr 2008 12:02:37 am Post subject: |
|
|
I have a feeling you don't really need to factor polynomials (much less in finite fields!) to solve your problem. There might be a simpler approach to check the "overlap" you speak of.
In any case, most of the polynomial factoring algorithms (that do not involve root extraction) are not too trivial to implement, and are quite complicated. The algorithm due to Cantor and Zassenhaus (see this) has in fact superseded the algorithm in this topic's title.
thornahawk |
|
| Back to top |
|
|
simonzack
Advanced Newbie
Joined: 25 Dec 2007
Posts: 71
|
| Posted: 08 Apr 2008 02:28:20 am Post subject: |
|
|
Your link gave me some "read only mode" error for some reason, do I have to be in some university with a user name and password to read it?
Quote: I have a feeling you don't really need to factor polynomials (much less in finite fields!) to solve your problem. There might be a simpler approach to check the "overlap" you speak of.
Is this about ring theory as well? |
|
| Back to top |
|
|
alexrudd
pm me if you read this
Bandwidth Hog
Joined: 06 Oct 2004
Posts: 2335
|
| Posted: 08 Apr 2008 12:48:55 pm Post subject: |
|
|
simonzack wrote: Your link gave me some "read only mode" error for some reason, do I have to be in some university with a user name and password to read it? [post="122278"]<{POST_SNAPBACK}>[/post] It worked fine for me in Firefox 3b5, but failed in IE7. If you are using Internet Explorer, try using a different browser. |
|
| Back to top |
|
|
simonzack
Advanced Newbie
Joined: 25 Dec 2007
Posts: 71
|
| Posted: 24 Apr 2008 01:38:15 am Post subject: |
|
|
Yeah, and I got that last thing (my aunt works at uni, so she has access to jstor after all :hmpf:, thus me)
Actually, now I've looked at it, abstract algebra sounds kind of interesting
Does anybody have some resources that I can learn it from? |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 24 Apr 2008 06:55:10 am Post subject: |
|
|
Well, "Algorithms for Computer Algebra" by Geddes et al. and the two "Computer Algebra and Symbolic Computation" books by Cohen are a place to start, but I must warn you that this is not for the (mathematically) faint-hearted. ;)
thornahawk |
|
| Back to top |
|
|
|
Math and Science => Technology & Calculator Open Topic
