בתשובה לאלון עמית, 02/08/06 11:19
 |
|
 |
||
|
||||
 |
ברור שזה לא ראוי לדפוס וברור שאמירות הרהב שם הם מגוחכות ומרגיזות. אוסף העובדות ה"מתמטי" המצוי שם הוא טריוואלי ומבולבל1. אבל סמיילי לא הבין בכלל מה הוא רצה, ולכן סיכמתי. מקובל עלי שמדובר ברשלנות חובבנית אגב, איך באמת קובעים ביעילות אם מספר רב סיפרתי הוא ריבוע של שלם? 1אהבתי במיוחד את הצמד: כל מספר זוגי נמצא בין שני מספרים אי זוגיים: 7 8 9 כל מספר אי זוגי נמצא בין שני מספרים זוגיים: 4 5 6 |
 |
 |
 |
|
|
|
||
|
||||
|
"כל מספר זוגי נמצא בין שני מספרים אי זוגיים: 7 8 9 כל מספר אי זוגי נמצא בין שני מספרים זוגיים: 4 5 6" זה פשוט לא נכון. בסדרה 2,4,6... *שום* מספר זוגי לא נמצא בין שני אי זוגיים. תרגיל: להמציא סדרה שבה שום אי-זוגי אינו נמצא בין מספרים זוגיים. |
|
|
|
|
|
|
||
|
||||
|
איך אתה יודע? בדקת את כל הסדרה? | |
|
|
|
|
|
||
|
||||
|
*אני* צריכה לבדוק? מה, אני פראיירית? שמתי מאבטח בכניסה, ותאמין לי - הוא מריח אי זוגיים מרחוק. הוא לא ייתן לאף אחד מהם להיכנס. | |
|
|
|
|
|
||
|
||||
|
כלומר, הכרזת על "ערב זוגיים"? | |
|
|
|
|
|
||
|
||||
|
תלוי למה אתה קורא "ביעילות". שיטת "אריה במדבר" תמצא את השורש הריבועי של N (אם הוא שלם) או תכריז שאין כזה (אם הוא לא שלם) בזמן (O(logN. (שזה שקול ל(O(N בגודל הקלט). יעיל מספיק? |
|
|
|
|
|
|
||
|
||||
|
יש שיטות יותר יעילות למשל http://en.wikipedia.org/wiki/Integer_square_root ועוד http://en.wikipedia.org/wiki/Category:Root-finding_a... | |
|
|
|
|
|
||
|
||||
|
אבל אני לא בהכרח רוצה *לחשב* את השורש, רק לדעת האם הוא שלם. האם אני חייב לבצע NR עד לנקודה מסויימת או שאפשר להסתפק ב"סימני התחלקות" כאלה ואחרים? | |
|
|
|
|
|
||
|
||||
|
קודם כל אני לא בטוח שאתה צודק, כי גם הכפל עצמו תורם (O(NlogN באורך הקלט אאל"ט. חוץ מזה קיוויתי שיש שיטה יותר טובה מחישוב ישיר של המכפלות. |
|
|
|
|
|
|
||
|
||||
|
ברור שיש וגם סיפקו לינקים. גם הפתרון הראשון שעלה בדעתי הוא יעיל מספיק. |
|
|
|
|
|
|
||
|
||||
|
מה שראיתי בלינקים השתמשו בחישוב ישיר של המכפלות, הם רק עשו אמדנים יותר מדוייקים משיטת החצייה בקשר לבחירת ערכי הבדיקה. זאת גם השיטה שאני הייתי נוקט. אני רוצה לדעת האם יש אלגוריתם שיכול לספק לי תשובה- שורש שלם או לא, ללא צורך בחישוב מפורש של השורש עצמו. במאמר בYNET היו כמה דוגמאות ל"כללי התחלקות" כאלו. |
|
|
|
|
|
|
||
|
||||
|
אם N אינו ריבועי, אז [[צפיפות דיריכלה]] של קבוצת הראשוניים שעבורם N הוא [[שארית ריבועית]] היא חצי. אפשר להפוך את ההצהרה הזו לאלגוריתם הסתברותי, שיבדיל ריבועים משאינם ריבועים בזמן קבוע כפול logN, בסיכוי שיורד אקספוננציאלית עם הקבוע. אם יש לגישה הזו גירסה דטרמיניסטית, אני לא מאמין שהיא תהיה טובה יותר מהוצאת השורש, שצריכה להיות (בכל שיטה שהיא) בעלת סיבוכיות logN-בריבוע. | |
|
|
|
|
|
||
|
||||
|
הראשוניים p כך ש-N איננו שארית ריבועית מודולו p מהווים "עדים" להיותו של N לא-ריבוע-שלם. אם N הוא כן ריבוע שלם, אין כאלה ראשוניים; אם הוא לא, יש הרבה כאלה ("בערך 50%" מכלל הראשוניים). | |
|
|
|
|
|
||
|
||||
|
אני הבנתי ששארית ריבועית היא פונקציה של שני דברים: מספר Mשמעלים אותו בריבוע, ומספר P שמחלקים בו את M^2 (בדרך כלל Pראשוני) הבנתי שאת הראשוני בוחרים אקראית (לפי התפלגות דיריכלה)מתוך הראשוניים, אבל לא הבנתי מיהו M. | |
|
|
|
|
|
||
|
||||
|
"N הוא שארית ריבועית מודולו p" אם יש מספר M כך ש-M^2 משאיר שארית N בחלוקה ל-p. בהינתן N ו-p, יש דרכים יעילות לבדוק אם N הוא כזה או לא (והן אינן כרוכות במציאת ה"שורש" M). אין לי טיפת זמן עכשיו אבל אשמח להרחיב אח"כ לגבי סימבול לז'נדר והדדיות ריבועית. | |
|
|
|
|
|
||
|
||||
|
אם הבנתי אותך, הרי שניסוח יותר ברור עבורי של המשפט הראשון בתגובה של עוזי הוא: אם N אינו ריבועי, אז [[צפיפות דיריכלה]] של קבוצת הראשוניים שעבורם N הוא [[שארית ריבועית]] עבור [[מחולק]] M *כלשהו* היא חצי. אני מוותר לך על ההרחבה, אבל *רק* בגלל שאתה כל כך עסוק :) |
|
|
|
|
|
|
||
|
||||
|
מה המשמעות של [[סוגריים מרובעים כפולים]]? | |
|
|
|
|
|
||
|
||||
|
"p הוא ראשוני שעבורו N הוא שארית ריבועית" = "N הוא שארית ריבועית מודולו p" = "קיים מספר x כך שהשארית של x^2 בחלוקה ל- p היא N". | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |