בתשובה לסמיילי, 02/08/06 9:20
האם יש שיטה לזיהוי מאמרים מטופשים? 400554
הוא מנסה למצוא שיטה ש
א) תזהה אם למספר כלשהו יש שורש *שלם*.
ב) בהנתן מספר שיש לו שורש שלם, תצליח למצוא אותו ביעילות.
האם יש שיטה לזיהוי מאמרים מטופשים? 400558
א) כדאי להזכיר ששיטות (פשוטות מאוד) לפתרון שאלות כאלה ידועות מזה מאות שנים.
ב) לא הבחנתי בהתייחסות ל"יעילות" (לא שזה היה משנה משהו).
ג) הוא רוצה גם להגיד (כמקובל במקרים כאלה, ראה דיון 1571 באתר "האייל הקורא") משהו על ההתעלמות התמוהה של קהילת המתמטיקאים מבעייה מרכזית זו, ומשהו על ייחודו שלו והישגיו ("למעשה, אני אפילו המצאתי את המונח").
האם יש שיטה לזיהוי מאמרים מטופשים? 400561
ניסיתי להבהיר לסמיילי את הקונטקסט של המאמר. בעניין היעילות נדמה לי שזה מובלע, שהרי תמיד אפשר לבדוק באופן פרטני.

אני מסכים שהערותיו על ההתעלמות התמוהה וכולי היא מסימני הטרחן(או לפחות הבור השחצן), אבל מעבר לאי דיוקים במינוח (הוא לא מבדיל בין קיום שורש ריבועי לבין קיום שורש ריבועי *שלם*), האם יש שם טעות מובהקת (גילוי נאות- לא טרחתי להתעמק בשיטות המופלאות)?
האם יש שיטה לזיהוי מאמרים מטופשים? 400574
הביטוי "טעות מובהקת", למרות חציו השני, הוא מעורפל קצת. הנה כמה אמירות שגויות או בעייתיות:

"מסיבה לא ברורה, לא מחפשים המתמטיקאים שיטה למצוא שורש ריבועי או שורש כלשהו." - הסיבה ברורה מאוד: חיפשו, מצאו (מזמן), והתקדמו לבעיות מעניינות יותר.

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

"ברם, שום ניסיון רציני לתקוף סוגיה זו לא נעשה, ואפילו לא מחפשים דרך כלשהי למצוא שורש ריבועי, של חלק מהמספרים הדו-חזקתיים" - "שטויות" זה "טעות מובהקת"?

"אין מספר דו-חזקתי אי זוגי שמסתיים בספרה 3" - זה משפט נכון, אבל תמוה. למה טרח הכותב לציין "אי זוגי"? כאילו, מספר דו-חזקתי (= ריבוע שלם) *זוגי* שמסתיים ב-‏3 יש? חוץ מזה, למה דווקא 3? גם אין ריבועים שלמים המסתיימים ב-‏2, 7 או 8.

"די בכך שתוצאת חלוקה של מספר זוגי בארבע תהא ללא שארית, כדי להצביע על כך שיתכן שהוא מספר דו-חזקתי, קרי שיש לו שורש ריבועי." - והייתי מוסיף, "די בכך שיש לזה זנב, כדי להצביע על כך שייתכן שזהו קרנף חירש". האם היית קורא לזה "טעות מובהקת"?

"באם הוא מספר אי זוגי יש לפעול לפי השיטה האי זוגית" - אם יש כזו, היא כנראה מתחבאת מאחורי הפיסקה עם נילס הולגרסן. אולי הכוונה ל"שורש ריבועי של מספר דו-חזקתי אי זוגי הוא תמיד סכום של שני מספרים עוקבים: 2+3=5". האם לקרוא לזה "שיטה" זו "טעות מובהקת"?

"עד כמה שידוע לי, אף אחד מלבדי בעולם לא מתעניין במספרים הללו" - מדובר על ריבועים שלמים. אנשים חוקרים אותם אלפי שנים.

ה"שיטה המופלאה" היחידה המתוארת כאן אומרת שאת שורשו של N אפשר למצוא ע"י מציאת שורשו של N/4, והכפלת התוצאה ב-‏2, *או* ע"י הוצאת שורש של N/16 והכפלת התוצאה ב-‏4 (חלוקה ב-‏64 תידון, ככל הנראה, במאמר המשך). האם זו "טעות מובהקת"? חלילה, זה נכון לגמרי. האם זה ראוי לדפוס? לא.
האם יש שיטה לזיהוי מאמרים מטופשים? 400578
ברור שזה לא ראוי לדפוס וברור שאמירות הרהב שם הם מגוחכות ומרגיזות. אוסף העובדות ה"מתמטי" המצוי שם הוא טריוואלי ומבולבל‏1. אבל סמיילי לא הבין בכלל מה הוא רצה, ולכן סיכמתי. מקובל עלי שמדובר ברשלנות חובבנית

אגב, איך באמת קובעים ביעילות אם מספר רב סיפרתי הוא ריבוע של שלם?

1אהבתי במיוחד את הצמד:
כל מספר זוגי נמצא בין שני מספרים אי זוגיים: 7 8 9
כל מספר אי זוגי נמצא בין שני מספרים זוגיים: 4 5 6
האם יש שיטה לזיהוי מאמרים מטופשים? 400585
"כל מספר זוגי נמצא בין שני מספרים אי זוגיים: 7 8 9
כל מספר אי זוגי נמצא בין שני מספרים זוגיים: 4 5 6"
זה פשוט לא נכון. בסדרה 2,4,6... *שום* מספר זוגי לא נמצא בין שני אי זוגיים.
תרגיל: להמציא סדרה שבה שום אי-זוגי אינו נמצא בין מספרים זוגיים.
האם יש שיטה לזיהוי תגובות מטופשות? 400589
איך אתה יודע? בדקת את כל הסדרה?
האם יש שיטה לזיהוי תגובות מטופשות? 400593
*אני* צריכה לבדוק? מה, אני פראיירית? שמתי מאבטח בכניסה, ותאמין לי - הוא מריח אי זוגיים מרחוק. הוא לא ייתן לאף אחד מהם להיכנס.
חילופי זוגות 400595
כלומר, הכרזת על "ערב זוגיים"?
חילופי זוגות 400598
לא ערב, מועדון.
האם יש שיטה לזיהוי מאמרים מטופשים? 400588
תלוי למה אתה קורא "ביעילות".
שיטת "אריה במדבר" תמצא את השורש הריבועי של N (אם הוא שלם) או תכריז שאין כזה (אם הוא לא שלם) בזמן (O(logN. (שזה שקול ל(O(N בגודל הקלט). יעיל מספיק?
האם יש שיטה לזיהוי מאמרים מטופשים? 400590
יש שיטות יותר יעילות למשל http://en.wikipedia.org/wiki/Integer_square_root ועוד http://en.wikipedia.org/wiki/Category:Root-finding_a...
האם יש שיטה לזיהוי מאמרים מטופשים? 400592
אבל אני לא בהכרח רוצה *לחשב* את השורש, רק לדעת האם הוא שלם. האם אני חייב לבצע NR עד לנקודה מסויימת או שאפשר להסתפק ב"סימני התחלקות" כאלה ואחרים?
האם יש שיטה לזיהוי מאמרים מטופשים? 400591
קודם כל אני לא בטוח שאתה צודק, כי גם הכפל עצמו תורם (O(NlogN באורך הקלט אאל"ט.
חוץ מזה קיוויתי שיש שיטה יותר טובה מחישוב ישיר של המכפלות.
האם יש שיטה לזיהוי מאמרים מטופשים? 400596
ברור שיש וגם סיפקו לינקים.
גם הפתרון הראשון שעלה בדעתי הוא יעיל מספיק.
האם יש שיטה לזיהוי מאמרים מטופשים? 400602
מה שראיתי בלינקים השתמשו בחישוב ישיר של המכפלות, הם רק עשו אמדנים יותר מדוייקים משיטת החצייה בקשר לבחירת ערכי הבדיקה. זאת גם השיטה שאני הייתי נוקט.

אני רוצה לדעת האם יש אלגוריתם שיכול לספק לי תשובה- שורש שלם או לא, ללא צורך בחישוב מפורש של השורש עצמו. במאמר בYNET היו כמה דוגמאות ל"כללי התחלקות" כאלו.
האם יש שיטה לזיהוי מאמרים מטופשים? 400709
אם N אינו ריבועי, אז [[צפיפות דיריכלה]] של קבוצת הראשוניים שעבורם N הוא [[שארית ריבועית]] היא חצי. אפשר להפוך את ההצהרה הזו לאלגוריתם הסתברותי, שיבדיל ריבועים משאינם ריבועים בזמן קבוע כפול logN, בסיכוי שיורד אקספוננציאלית עם הקבוע. אם יש לגישה הזו גירסה דטרמיניסטית, אני לא מאמין שהיא תהיה טובה יותר מהוצאת השורש, שצריכה להיות (בכל שיטה שהיא) בעלת סיבוכיות logN-בריבוע.
פתחתי ויקיפדיה 400733
[[שארית ריבועית]] מודולו מה?
פתחתי ויקיפדיה 400738
הראשוניים p כך ש-N איננו שארית ריבועית מודולו p מהווים "עדים" להיותו של N לא-ריבוע-שלם. אם N הוא כן ריבוע שלם, אין כאלה ראשוניים; אם הוא לא, יש הרבה כאלה ("בערך 50%" מכלל הראשוניים).
פתחתי ויקיפדיה 400739
אני הבנתי ששארית ריבועית היא פונקציה של שני דברים: מספר Mשמעלים אותו בריבוע, ומספר P שמחלקים בו את M^2 (בדרך כלל Pראשוני) הבנתי שאת הראשוני בוחרים אקראית (לפי התפלגות דיריכלה)מתוך הראשוניים, אבל לא הבנתי מיהו M.
פתחתי ויקיפדיה 400917
"N הוא שארית ריבועית מודולו p" אם יש מספר M כך ש-M^2 משאיר שארית N בחלוקה ל-p. בהינתן N ו-p, יש דרכים יעילות לבדוק אם N הוא כזה או לא (והן אינן כרוכות במציאת ה"שורש" M). אין לי טיפת זמן עכשיו אבל אשמח להרחיב אח"כ לגבי סימבול לז'נדר והדדיות ריבועית.
פתחתי ויקיפדיה 400925
אם הבנתי אותך, הרי שניסוח יותר ברור עבורי של המשפט הראשון בתגובה של עוזי הוא:

אם N אינו ריבועי, אז [[צפיפות דיריכלה]] של קבוצת הראשוניים שעבורם N הוא [[שארית ריבועית]] עבור [[מחולק]] M *כלשהו* היא חצי.

אני מוותר לך על ההרחבה, אבל *רק* בגלל שאתה כל כך עסוק :)
פתחתי ויקיפדיה 400929
מה המשמעות של [[סוגריים מרובעים כפולים]]?
פתחתי ויקיפדיה 400931
הפניה לערך אחר באנציקלופדיה.
פתחתי ויקיפדיה 400932
"p הוא ראשוני שעבורו N הוא שארית ריבועית" = "N הוא שארית ריבועית מודולו p" = "קיים מספר x כך שהשארית של x^2 בחלוקה ל- p היא N".
Now you tell me 400933

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים