אריתמטיקת טבעיים

אריתמטיקת טבעיים

מעניין אותי לדעת האם מישהו מכיר שילוב טוב של מבני נתונים + אלגוריתמים המאפשרים פעולות חיבור/חיסור/כפל מאד מהירות על מספרים טבעיים? אפשר תמיד תייצג אותם בתור מערך של ספרות בבסיס ספירה כלשהו, לחבר עם "חיבור ארוך" ולכפול עם משהו מבוסס התמרת פוריה (או משהו יותר מתוחכם אבל דומה). חשבתי אולי שאם נייצג אותם בצורה שונה, לא בתור מערך של ספרות, יתכן וזה יעבוד יותר מהר. רעיונות?
 

vinney

Well-known member
המם...

אני חושב שבחישובים קוואנטיים עושים כאלה דברים, בחישוב סדרתי רגיל זה קצת בעיה לחשב את הביט הN, לפני שחישבת את הביטים לפניו... בכל מקרה, קח את הפרק של קורמן המתעסק באלגוריתמים מתורת המספרים, תהנה
 

DNile

New member
הוא רוצה שתסביר לו

איך משתמשים בהתמרות פוריה כדי לבצע כפל מהיר.
 
../images/Emo45.gif אבל יש התאמה בין פולינומים

למספרים טבעיים. למשל:
1387 ~ f(x) = 1*x^3 + 3*x^2 + 8*x + 7​
כאשר X=10. אז כל אלגוריתם שיתאים לפולינומים, יתאים גם למספרים טבעיים.
 
יש אלגוריתמים כמו של

nussbaumer או karatsuba שיעשו שיכפלו מספרים די מהר. אבל הכי טוב הוא האלגוריתם של Schönhage-Strassen
 
למעלה