127. BigInteger

מדי פעם אנחנו נתקלים בחישובים עם מספרים גדולים. למרבה הצער, הטיפוסים הפרימיטיביים של C# מוגבלים בטווח שלהם.

למשל, אם ננסה לחשב עצרת של 100:

public static long Factorial(long n)
{
    long result = 1;
      
    for (long i = 1; i <= n; i++)
    {
        result *= i;
    }

    return result;
}

עד כמה שlong הוא גדול, נקבל את התוצאה הבאה בחישוב עצרת של 100: 0.

הסיבה היא שlong מוגבל עד $ 2^{63}$, אבל 100 עצרת יותר גדול מ$ 2^{524} $.

כדי לפתור בעיה זו בכל זאת, הומצא לנו בC# 4.0 טיפוס חדש ששמו BigInteger (יושב בSystem.Numerics בSystem.Numerics.dll). הטיפוס מאפשר לנו להגדיר מספר שלם גדול כרצוננו בזכרון. (הדבר עובד מאחורי הקלעים עם מערך של uint המייצג את המספר).

כך אנחנו יכולים לבצע חישובים כבדים שהגבולות שלהם תלויים רק בגודל הזכרון שלנו. לדוגמה:

public static BigInteger Factorial(int n)
{
    BigInteger result = 1;

    for (int i = 1; i <= n; i++)
    {
        result *= i;
    }

    return result;
}

שימו לב שקיימים אופרטורים מתאימים לפעולות חשבון הבסיסיות שמקבלים גם BigInteger וגם טיפוסים נומריים פרימטיביים אחרים, כך שאנחנו יכולים להכפיל BigInteger בint ללא שום בעיה.

כמה דברים נחמדים: למי שתהה:

עצרת של מאה זה בסה"כ

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

שימו לב שיש הרבה פונקציות סטטיות של BigInteger המאפשרים לנו לחשב חזקה וכו’.

ואיך אפשר לכתוב טיפ יומי על BigInteger ביום שכזה בלי לציין את הדוגמה הבאה:

public static BigInteger FirstDigits(int numOfDigits)
{
    int loopIterations = (int)(numOfDigits * Math.Log(10, 4)) + 2;

    BigInteger result = 0;

    int odd = 1;
    int minus = 1;

    BigInteger two = 2;
    BigInteger three = 3;
    BigInteger current = 4 * BigInteger.Pow(10, numOfDigits);

    for (int i = 1; i <= loopIterations; i++)
    {
        result += minus * current / (two * odd) + 
                  minus * current / (three * odd);

        minus *= -1;
        odd += 2;
        two *= 2 * 2;
        three *= 3 * 3;
    }

    return result;
}

תוכלו לנחש מה זה עושה? רמז: אם נעביר 100 לפונקציה נקבל את התוצאה הבאה:

31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170683

(אם יש למישהו כוח לבדוק למה יש טעות ב3 ספרות האחרונות (אמור להיות 798 במקום 683), אני אשמח שישתף אותי)

המשך יום פאי שמח