משתנים ב -C

[Ghosthunter]

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

[nehmia]

תקשיבו...אני בסהך מתכנת מתחיל...אני לא באמת מבין הרבה...אין איזה משתנה כזה?

[icebreak]

אם אתה מתחיל, אז מה אתה צריך דברים כאלו ?

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

בכל מקרה, המשתנה הכי גדול שיש בשפה זה LONG DOUBLE, צריך לבדוק כמה הוא יכול לאכסן (אם כי לא נראה לי שהוא יגיע לגדלים שרצית).

[nehmia]

LONG DOUBLE הוא 19 ספרות

אני רוצה ספרייה אם משתנים ממש ממש גדולים...

[icebreak]

http://www.tc.umn.edu/~ringx004/mapm-main.html

[nehmia]

הנה מצאתי את זה אבל לא הבנתי....

In an arbitrary precision math library, the multiplication function is the most critical. Multiplication is normally an O(N2) operation. When you learned to multiply in grade school, you multiplied each digit of each number and did the final addition after all the multiplies were completed. To visualize this, multiply by hand a four-digit number by a four-digit number. The intermediate math requires 16 multiplies (42). This method works and is very easy to implement; however it becomes prohibitively slow when the number of digits becomes large. So a 10,000-digit multiply will require 100 million individual multiplications!

Faster Multiplication

The next multiplication algorithm discussed is commonly referred to as the divide-and-conquer algorithm.

Assume we have two numbers (a and b) each containing 2N digits:

let: a = (2N)*A1 + A0, b = (2N)*B1 + B0

where A1 is the "most significant half" of a and A0 is the "least significant half" of a. The same applies for B1 and B0.

Now use the identity:

ab = (22N + 2N)A1B1 + 2N(A1-A0)(B0-B1) + (2N + 1)A0B0

The original problem of multiplying two 2N-digit numbers has been reduced to three multiplications of N-digit numbers plus some additions, subtractions, and shifts.

This multiplication algorithm can be used in a recursive process. The divide-and-conquer method results in approximately O(N1.585) growth in computing time as N increases. So a 10,000-digit multiply will result in only approximately 2.188 million multiplies. This represents a considerable improvement over the generic O(N2) method.

[icebreak]

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

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

הכפל המהיר שמתואר פה לוקח רק N בחזקת 1.585, שזה כמובן פתרון עדיף / מהיר יותר.

(כמובן שמדובר פה בחסמים אסימפטוטים ולא חישובים מדויקים).