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

[IsraeliSecretToilets]

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

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

 

[vinney]

המם...

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

 

[yossiea]

"מבוסס התמרת פוריה" ???

 

[IsraeliSecretToilets]

מה השאלה בדיוק?

 

[DNile]

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

איך משתמשים בהתמרות פוריה כדי לבצע כפל מהיר.

 

[מרטין מקפליי]

משתמשים בהתמרת פוריה לכפל פולינומים

לא לכפל רגיל...

 

[ה עוד אחד]

../images/Emo45.gif אבל יש התאמה בין פולינומים

למספרים טבעיים. למשל:

1387 ~ f(x) = 1*x^3 + 3*x^2 + 8*x + 7​

כאשר X=10. אז כל אלגוריתם שיתאים לפולינומים, יתאים גם למספרים טבעיים.

 

[מרטין מקפליי]

צודק

 

[ה עוד אחד]

יש אלגוריתמים כמו של

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

 

[ה עוד אחד]

שיעשו שיכפלו == שיכפלו

 

[ASP zone]

פרט עוד

נשמע מעניין.

 

[IsraeliSecretToilets]

השתמש בגוגל

העוזר האישי שלך