בתשובה לאלון עמית, 02/08/06 8:24
 |
|
 |
||
|
||||
 |
עורך? קודם כל הם צריכים מתרגם (או, במילים אחרות, מישהו מוכן להסביר לי בעברית מה הוא רוצה להגיד). |  |
 |
 |
|
|
|
||
|
||||
|
הוא מנסה למצוא שיטה ש א) תזהה אם למספר כלשהו יש שורש *שלם*. ב) בהנתן מספר שיש לו שורש שלם, תצליח למצוא אותו ביעילות. |
|
|
|
|
|
|
||
|
||||
|
א) כדאי להזכיר ששיטות (פשוטות מאוד) לפתרון שאלות כאלה ידועות מזה מאות שנים. ב) לא הבחנתי בהתייחסות ל"יעילות" (לא שזה היה משנה משהו). ג) הוא רוצה גם להגיד (כמקובל במקרים כאלה, ראה דיון 1571 באתר "האייל הקורא") משהו על ההתעלמות התמוהה של קהילת המתמטיקאים מבעייה מרכזית זו, ומשהו על ייחודו שלו והישגיו ("למעשה, אני אפילו המצאתי את המונח"). |
|
|
|
|
|
|
||
|
||||
|
ניסיתי להבהיר לסמיילי את הקונטקסט של המאמר. בעניין היעילות נדמה לי שזה מובלע, שהרי תמיד אפשר לבדוק באופן פרטני. אני מסכים שהערותיו על ההתעלמות התמוהה וכולי היא מסימני הטרחן(או לפחות הבור השחצן), אבל מעבר לאי דיוקים במינוח (הוא לא מבדיל בין קיום שורש ריבועי לבין קיום שורש ריבועי *שלם*), האם יש שם טעות מובהקת (גילוי נאות- לא טרחתי להתעמק בשיטות המופלאות)? |
|
|
|
|
|
|
||
|
||||
|
הביטוי "טעות מובהקת", למרות חציו השני, הוא מעורפל קצת. הנה כמה אמירות שגויות או בעייתיות: "מסיבה לא ברורה, לא מחפשים המתמטיקאים שיטה למצוא שורש ריבועי או שורש כלשהו." - הסיבה ברורה מאוד: חיפשו, מצאו (מזמן), והתקדמו לבעיות מעניינות יותר. "חידת המספרים הראשוניים היא שמונעת מציאת השיטה לכאורה, ועד שלא תיפתר, אין על מה לדבר." - זה משפט כל כך תמוה שקשה אפילו לסווגו כ"טעות מובהקת". הוא ודאי לא אמת, והוא אפילו לא שקר. "ברם, שום ניסיון רציני לתקוף סוגיה זו לא נעשה, ואפילו לא מחפשים דרך כלשהי למצוא שורש ריבועי, של חלק מהמספרים הדו-חזקתיים" - "שטויות" זה "טעות מובהקת"? "אין מספר דו-חזקתי אי זוגי שמסתיים בספרה 3" - זה משפט נכון, אבל תמוה. למה טרח הכותב לציין "אי זוגי"? כאילו, מספר דו-חזקתי (= ריבוע שלם) *זוגי* שמסתיים ב-3 יש? חוץ מזה, למה דווקא 3? גם אין ריבועים שלמים המסתיימים ב-2, 7 או 8. "די בכך שתוצאת חלוקה של מספר זוגי בארבע תהא ללא שארית, כדי להצביע על כך שיתכן שהוא מספר דו-חזקתי, קרי שיש לו שורש ריבועי." - והייתי מוסיף, "די בכך שיש לזה זנב, כדי להצביע על כך שייתכן שזהו קרנף חירש". האם היית קורא לזה "טעות מובהקת"? "באם הוא מספר אי זוגי יש לפעול לפי השיטה האי זוגית" - אם יש כזו, היא כנראה מתחבאת מאחורי הפיסקה עם נילס הולגרסן. אולי הכוונה ל"שורש ריבועי של מספר דו-חזקתי אי זוגי הוא תמיד סכום של שני מספרים עוקבים: 2+3=5". האם לקרוא לזה "שיטה" זו "טעות מובהקת"? "עד כמה שידוע לי, אף אחד מלבדי בעולם לא מתעניין במספרים הללו" - מדובר על ריבועים שלמים. אנשים חוקרים אותם אלפי שנים. ה"שיטה המופלאה" היחידה המתוארת כאן אומרת שאת שורשו של N אפשר למצוא ע"י מציאת שורשו של N/4, והכפלת התוצאה ב-2, *או* ע"י הוצאת שורש של N/16 והכפלת התוצאה ב-4 (חלוקה ב-64 תידון, ככל הנראה, במאמר המשך). האם זו "טעות מובהקת"? חלילה, זה נכון לגמרי. האם זה ראוי לדפוס? לא. |
|
|
|
|
|
|
||
|
||||
|
ברור שזה לא ראוי לדפוס וברור שאמירות הרהב שם הם מגוחכות ומרגיזות. אוסף העובדות ה"מתמטי" המצוי שם הוא טריוואלי ומבולבל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 מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |