כפל מודולרי

עריסטו · 2/9/24

אתם עובדים בשפת תכנות שבה כל המספרים הם מסוג signed 32-bit integer כלומר הם יכולים להיות כל ערך שלם בין 2147483648- ל-2147483647. אם תוצאת חישוב חורגת מהתחום הזה מתקבלת הודעת שגיאה. אתם רוצים לכתוב תוכנית שמקבלת מספר שלם x בין 0 ל-2147483646 ומחשבת את
52879x MOD 2147483647 (השארית מחילוק 52879x ב-2147483647). כמובן אי אפשר לחשב זאת ישירות כי עבור רוב הערכים של x המספר 52879x גדול מ-2147483647 ומתקבלת שגיאה. מהי הדרך המהירה והפשוטה ביותר לבצע את החישוב?

הפרבולה1 · 11/9/24

נכתב ע"י עריסטו:
אתם עובדים בשפת תכנות שבה כל המספרים הם מסוג signed 32-bit integer כלומר הם יכולים להיות כל ערך שלם בין 2147483648- ל-2147483647. אם תוצאת חישוב חורגת מהתחום הזה מתקבלת הודעת שגיאה. אתם רוצים לכתוב תוכנית שמקבלת מספר שלם x בין 0 ל-2147483646 ומחשבת את
52879x MOD 2147483647 (השארית מחילוק 52879x ב-2147483647). כמובן אי אפשר לחשב זאת ישירות כי עבור רוב הערכים של x המספר 52879x גדול מ-2147483647 ומתקבלת שגיאה. מהי הדרך המהירה והפשוטה ביותר לבצע את החישוב?

דרך אחת ( שלא בטוח שהיא הכי מהירה ופשוטה) זה לחבר את המספר 52879 x פעמים , אחרי כל פעולת חיבור לבדוק את ההפרש בין הסכום שניצבר לבין 2147483647 , אם ההפרש קטן או שווה ל 52879 אז להחסיר מהסכום שניצבר 2147483647 כדי לא לעבור את התחום של signed 32-bit integer ולהמשיך בחיבור החוזר .

בסיום אם התוצאה שלילית יש להוסיף 2147483647 כדי לקבל את השארית בתחום 0 ....2147483646

עריסטו · 11/9/24

נכתב ע"י הפרבולה1:
דרך אחת ( שלא בטוח שהיא הכי מהירה ופשוטה) זה לחבר את המספר 52879 x פעמים , אחרי כל פעולת חיבור לבדוק את ההפרש בין הסכום שניצבר לבין 2147483647 , אם ההפרש קטן או שווה ל 52879 אז להחסיר מהסכום שניצבר 2147483647 כדי לא לעבור את התחום של signed 32-bit integer ולהמשיך בחיבור החוזר .

בסיום אם התוצאה שלילית יש להוסיף 2147483647 כדי לקבל את השארית בתחום 0 ....2147483646

יש דרכים מהירות יותר.

הפרבולה1 · 22/9/24

נכתב ע"י עריסטו:
יש דרכים מהירות יותר.

עוד דרך.
מאחר שהמספר 52879 נתון מראש , נחשב מראש ( נגיד עם מחשבון ) את השאריות של 52879 *1 52879 *2 52879 *4 52879 *8 ...... 52879 *(31^2) בחילוק ב 2147483647 .
נאכסן את השאריות האלו זאת בטבלה של 31 מקומות ( שהתאים שלה ממוספרים 1...31 ).

כעת בהנתן x כשלהוא נעבור על ההצגה הבינרית שלו ואם הביט ה n שווה ל1 נוסיף לסכום מצטבר את מה שכתוב בטבלה במקום ה n , לפני כל חיבור נבדוק שלא תהיה גלישה על ידי בדיקת ההפרש בין 2147483647 לסכום שניצבר והשוואתו לשארית שעומדים להוסיף , ואם גדול שווה אז קודם להחסיר 2147483647 מהסכום שניצבר ( כמו מקודם )

בסיום אם התוצאה שלילית יש להוסיף 2147483647 כדי לקבל את השארית בתחום 0 ....2147483646.

ההבדל מהדרך הקודמת שהסיבוכיות היא רק בגודל 31 כמספר הביטים ולא כגודל x.

עריסטו · 22/9/24

נכתב ע"י הפרבולה1:
עוד דרך.
מאחר שהמספר 52879 נתון מראש , נחשב מראש ( נגיד עם מחשבון ) את השאריות של 52879 *1 52879 *2 52879 *4 52879 *8 ...... 52879 *(31^2) בחילוק ב 2147483647 .
נאכסן את השאריות האלו זאת בטבלה של 31 מקומות ( שהתאים שלה ממוספרים 1...31 ).

כעת בהנתן x כשלהוא נעבור על ההצגה הבינרית שלו ואם הביט ה n שווה ל1 נוסיף לסכום מצטבר את מה שכתוב בטבלה במקום ה n , לפני כל חיבור נבדוק שלא תהיה גלישה על ידי בדיקת ההפרש בין 2147483647 לסכום שניצבר והשוואתו לשארית שעומדים להוסיף , ואם גדול שווה אז קודם להחסיר 2147483647 מהסכום שניצבר ( כמו מקודם )

בסיום אם התוצאה שלילית יש להוסיף 2147483647 כדי לקבל את השארית בתחום 0 ....2147483646.

ההבדל מהדרך הקודמת שהסיבוכיות היא רק בגודל 31 כמספר הביטים ולא כגודל x.

זה שיפור אבל יש דרך מהירה ופשוטה יותר.

Lucifer LightBringer · 3/9/24

לא פשוט לקחת את ההפרש בין 214783647-52879x בערך מוחלט ואז למצוא את השארית, אם המספר עדיין גדול מידי להמשיך להחסיר עד שהמספר קטן מהחסם העליון ואז למצוא שארית.

אולי אני מפספס משהו פה? בדרך כלל השאלות שלך קשות אז בטח החמצתי פה משהו.

עריסטו · 3/9/24

לא ברור לי מה הפתרון. איך אתה מחשב את ההפרש שכתבת כאשר חישוב של 52879x גורם לשגיאה?

Lucifer LightBringer · 3/9/24

אז להשתמש במשפט ווילסון?
לא בטוח, האם המספר הזה 2147483647 הוא ראשוני או פריק.
בטח אפשר להשתמש במתמטיקה ולבדוק בטח יש להם פקודה כזו IsPrime.

אחשוב על זה יותר מאוחר.

Lucifer LightBringer · 7/9/24

ממתי למספר יש ערך בוויקיפדיה?!

2,147,483,647 - Wikipedia

en.wikipedia.org

טוב אז נראה לי שאפשר לחשב את השארית של 52879 בחילוק ב-2147483647 ולחבר אותה לשארית של x ב-2147483647. המספר לא לחצות את הגבולות של 32-bit integer.
אבל חשבתי שרוב המחשבים עכשיו עובדים על 64 ביט.

הפרבולה1 · 2/10/24

עוד דרך ( נסמן y=52879 )
את x אפשר להציג ככה zzz x= m1 + m2*2^15 + m3 * 2^30 zzz
כאשר
m1 זה המספר שמיוצג על ידי ביטים 0...14
m2 זה המספר שמיוצג על ידי ביטים 15...29
m3 זה המספר שמיוצג על ידי ביט 30

ואז x*y שווה zzz x*y= m1*y + m2*y*2^15 + m3*y * 2^30 zzz
m1*y m2*y m3*y הם כולם קטנים מ 2147483647 ולכן אין בעיה לבצע זאת .

טענה : השארית של zzz a * 2^n zzz בחילוק ב 2147483647 כאשר a בתחום 0....2147483647 מתקבלת על ידי הזזה שמאלה ציקלית n ביטים סביב 31 הביטים הראשונים ( למשל הזזה ב n=1 מעביר את ביט 0 לביט 1, ביט 1 לביט 2, ..... ביט 30 לביט 0 ).
ולכן אחרי שמבצעים את m1*y m2*y m3*y מחשבים את השארית של כל אחד מהאברים m1*y , m2*y*2^15, m3*y * 2^30 באמצעות הזזה ציקלית מתאימה.
מסכמים את 3 השאריות ( כולל בדיקה לפני כל חיבור שלא תהיה גלישה ואם כן מחסירים קודם 2147483647 מהסכום).

הנה פונקציה ב C

C:

int reminder31( int x, int y=52879)
{
       //x = m1  + m2*2^15 +m3*2^30  where m1=bit 0...14   , m2 = bit 15...29, m3 =bit 30
       int M = 0x7fffffff; // = 2147483647
       int m1,m2,m3;
       m1= x & 0x7fff;
       int r1 = m1 * y;

       m2= (x>>15)  &0x7fff;
       int bb = m2 * y;
       int r2 =  ((bb&0xffff)<<15) + (bb>>(31-15));

       m3= (x>>30);
       int cc = m3 * y;
       int r3 =  (((cc&0xffff)<<30)& M) + (cc>>(31-30));
  
       int r=r1;
       if(M-r<=r2){ // test to not overflow  32bit signed integer
              r-=M;
       }
       r += r2;

       if(M-r<=r3){ // test to not overflow  32bit signed integer
              r-=M;
       }
       r+=r3;
       return r;
}

עריסטו · 2/10/24

נכתב ע"י הפרבולה1:
עוד דרך ( נסמן y=52879 )
את x אפשר להציג ככה zzz x= m1 + m2*2^15 + m3 * 2^30 zzz
כאשר
m1 זה המספר שמיוצג על ידי ביטים 0...14
m2 זה המספר שמיוצג על ידי ביטים 15...29
m3 זה המספר שמיוצג על ידי ביט 30

ואז x*y שווה zzz x*y= m1*y + m2*y*2^15 + m3*y * 2^30 zzz
m1*y m2*y m3*y הם כולם קטנים מ 2147483647 ולכן אין בעיה לבצע זאת .

טענה : השארית של zzz a * 2^n zzz בחילוק ב 2147483647 כאשר a בתחום 0....2147483647 מתקבלת על ידי הזזה שמאלה ציקלית n ביטים סביב 31 הביטים הראשונים ( למשל הזזה ב n=1 מעביר את ביט 0 לביט 1, ביט 1 לביט 2, ..... ביט 30 לביט 0 ).
ולכן אחרי שמבצעים את m1*y m2*y m3*y מחשבים את השארית של כל אחד מהאברים m1*y , m2*y*2^15, m3*y * 2^30 באמצעות הזזה ציקלית מתאימה.
מסכמים את 3 השאריות ( כולל בדיקה לפני כל חיבור שלא תהיה גלישה ואם כן מחסירים קודם 2147483647 מהסכום).

הנה פונקציה ב C

C:

int reminder31( int x, int y=52879) { //x = m1 + m2*2^15 +m3*2^30 where m1=bit 0...14 , m2 = bit 15...29, m3 =bit 30 int M = 0x7fffffff; // = 2147483647 int m1,m2,m3; m1= x & 0x7fff; int r1 = m1 * y; m2= (x>>15) &0x7fff; int bb = m2 * y; int r2 = ((bb&0xffff)<<15) + (bb>>(31-15)); m3= (x>>30); int cc = m3 * y; int r3 = (((cc&0xffff)<<30)& M) + (cc>>(31-30)); int r=r1; if(M-r<=r2){ // test to not overflow 32bit signed integer r-=M; } r += r2; if(M-r<=r3){ // test to not overflow 32bit signed integer r-=M; } r+=r3; return r; }

יש פתרון קצר ופשוט יותר (שלוש שורות ב-C).

הפרבולה1 · 6/10/24

נכתב ע"י עריסטו:
יש פתרון קצר ופשוט יותר (שלוש שורות ב-C).

אפשר רמז ?

עריסטו · 7/10/24

נכתב ע"י הפרבולה1:
אפשר רמז ?

הפתרון לא משתמש בעובדה ש-2147483647 קטן ב-1 מחזקה של 2. הוא פועל עם כל מספר אחר במקום 2147483647.

הפרבולה1 · 7/10/24

נכתב ע"י עריסטו:
הפתרון לא משתמש בעובדה ש-2147483647 קטן ב-1 מחזקה של 2. הוא פועל עם כל מספר אחר במקום 2147483647.

הפונקציה int reminder( int x) מקבלת את x בין 0 ל 2147483646 ומחזירה את השארית בחילוק ב 2147483647 של 52879x.

C:

     int M = 0x7fffffff; // = 2147483647
     int y=52879;
     int ry = M % y;
     int n= (M-ry)/y; // M = n*y+ry

int reminder( int x)
{
     int rx =x % n;
     int a =(x-rx)/n;  // x =  a*n + rx
     int r =-a*ry + rx*y; // x*y = (a*n+rx)*y = a*n*y + rx*y = (MODE M) = -a*ry + rx*y
     if(r<0) {
         r+=M;
     }
     return r;
}

עריסטו · 7/10/24

נכתב ע"י הפרבולה1:
הפונקציה int reminder( int x) מקבלת את x בין 0 ל 2147483646 ומחזירה את השארית בחילוק ב 2147483647 של 52879x.

C:

int M = 0x7fffffff; // = 2147483647 int y=52879; int ry = M % y; int n= (M-ry)/y; // M = n*y+ry int reminder( int x) { int rx =x % n; int a =(x-rx)/n; // x = a*n + rx int r =-a*ry + rx*y; // x*y = (a*n+rx)*y = a*n*y + rx*y = (MODE M) = -a*ry + rx*y if(r<0) { r+=M; } return r; }

נכון, ודרך אגב אפשר לקצר ולכתוב
int n=M/y
int a=x/n
כלומר אין צורך לחסר את השארית לפני שמחלקים (בשפת C חילוק של מספרים מסוג int קוטע את החלק שאחרי הנקודה העשרונית, למשל 100/7=14).
הנה החישוב בקיצור:
int m = 52879 * (x % 40611) - 14578 * (x / 40611);
if (m < 0)
m = m + 2147483647;

כפל מודולרי

עריסטו

Active member

הפרבולה1

Well-known member

עריסטו

Active member

הפרבולה1

Well-known member

עריסטו

Active member

Lucifer LightBringer

Well-known member

עריסטו

Active member

Lucifer LightBringer

Well-known member

Lucifer LightBringer

Well-known member

2,147,483,647 - Wikipedia

הפרבולה1

Well-known member

עריסטו

Active member

הפרבולה1

Well-known member

עריסטו

Active member

הפרבולה1

Well-known member

עריסטו

Active member