בתשובה לראובן, 02/08/06 11:40
האם יש שיטה לזיהוי מאמרים מטופשים? 400588
easy • בתשובה לראובן יום ד', 2/8/2006, 12:01
תלוי למה אתה קורא "ביעילות".
שיטת "אריה במדבר" תמצא את השורש הריבועי של N (אם הוא שלם) או תכריז שאין כזה (אם הוא לא שלם) בזמן (O(logN. (שזה שקול ל(O(N בגודל הקלט). יעיל מספיק?
האם יש שיטה לזיהוי מאמרים מטופשים? 400590
האייל האלמוני • בתשובה לeasy יום ד', 2/8/2006, 12:05
יש שיטות יותר יעילות למשל http://en.wikipedia.org/wiki/Integer_square_root ועוד http://en.wikipedia.org/wiki/Category:Root-finding_a...
האם יש שיטה לזיהוי מאמרים מטופשים? 400592
ראובן • בתשובה להאייל האלמוני יום ד', 2/8/2006, 12:11
אבל אני לא בהכרח רוצה *לחשב* את השורש, רק לדעת האם הוא שלם. האם אני חייב לבצע NR עד לנקודה מסויימת או שאפשר להסתפק ב"סימני התחלקות" כאלה ואחרים?
האם יש שיטה לזיהוי מאמרים מטופשים? 400591
ראובן • בתשובה לeasy יום ד', 2/8/2006, 12:09
קודם כל אני לא בטוח שאתה צודק, כי גם הכפל עצמו תורם (O(NlogN באורך הקלט אאל"ט.
חוץ מזה קיוויתי שיש שיטה יותר טובה מחישוב ישיר של המכפלות.
האם יש שיטה לזיהוי מאמרים מטופשים? 400596
easy • בתשובה לראובן יום ד', 2/8/2006, 12:35
ברור שיש וגם סיפקו לינקים.
גם הפתרון הראשון שעלה בדעתי הוא יעיל מספיק.
האם יש שיטה לזיהוי מאמרים מטופשים? 400602
ראובן • בתשובה לeasy יום ד', 2/8/2006, 13:09
מה שראיתי בלינקים השתמשו בחישוב ישיר של המכפלות, הם רק עשו אמדנים יותר מדוייקים משיטת החצייה בקשר לבחירת ערכי הבדיקה. זאת גם השיטה שאני הייתי נוקט.

אני רוצה לדעת האם יש אלגוריתם שיכול לספק לי תשובה- שורש שלם או לא, ללא צורך בחישוב מפורש של השורש עצמו. במאמר בYNET היו כמה דוגמאות ל"כללי התחלקות" כאלו.
האם יש שיטה לזיהוי מאמרים מטופשים? 400709
עוזי ו. • בתשובה לראובן יום ד', 2/8/2006, 19:25
אם N אינו ריבועי, אז [[צפיפות דיריכלה]] של קבוצת הראשוניים שעבורם N הוא [[שארית ריבועית]] היא חצי. אפשר להפוך את ההצהרה הזו לאלגוריתם הסתברותי, שיבדיל ריבועים משאינם ריבועים בזמן קבוע כפול logN, בסיכוי שיורד אקספוננציאלית עם הקבוע. אם יש לגישה הזו גירסה דטרמיניסטית, אני לא מאמין שהיא תהיה טובה יותר מהוצאת השורש, שצריכה להיות (בכל שיטה שהיא) בעלת סיבוכיות logN-בריבוע.
פתחתי ויקיפדיה 400733
ראובן • בתשובה לעוזי ו. יום ה', 3/8/2006, 9:37
[[שארית ריבועית]] מודולו מה?
פתחתי ויקיפדיה 400738
אלון עמית • בתשובה לראובן יום ה', 3/8/2006, 9:56
הראשוניים p כך ש-N איננו שארית ריבועית מודולו p מהווים "עדים" להיותו של N לא-ריבוע-שלם. אם N הוא כן ריבוע שלם, אין כאלה ראשוניים; אם הוא לא, יש הרבה כאלה ("בערך 50%" מכלל הראשוניים).
פתחתי ויקיפדיה 400739
ראובן • בתשובה לאלון עמית יום ה', 3/8/2006, 10:03
אני הבנתי ששארית ריבועית היא פונקציה של שני דברים: מספר Mשמעלים אותו בריבוע, ומספר P שמחלקים בו את M^2 (בדרך כלל Pראשוני) הבנתי שאת הראשוני בוחרים אקראית (לפי התפלגות דיריכלה)מתוך הראשוניים, אבל לא הבנתי מיהו M.
פתחתי ויקיפדיה 400917
אלון עמית • בתשובה לראובן יום ה', 3/8/2006, 17:35
"N הוא שארית ריבועית מודולו p" אם יש מספר M כך ש-M^2 משאיר שארית N בחלוקה ל-p. בהינתן N ו-p, יש דרכים יעילות לבדוק אם N הוא כזה או לא (והן אינן כרוכות במציאת ה"שורש" M). אין לי טיפת זמן עכשיו אבל אשמח להרחיב אח"כ לגבי סימבול לז'נדר והדדיות ריבועית.
פתחתי ויקיפדיה 400925
ראובן • בתשובה לאלון עמית יום ה', 3/8/2006, 17:55
אם הבנתי אותך, הרי שניסוח יותר ברור עבורי של המשפט הראשון בתגובה של עוזי הוא:

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

אני מוותר לך על ההרחבה, אבל *רק* בגלל שאתה כל כך עסוק :)
פתחתי ויקיפדיה 400929
סמיילי • בתשובה לראובן יום ה', 3/8/2006, 17:57
מה המשמעות של [[סוגריים מרובעים כפולים]]?
פתחתי ויקיפדיה 400931
ראובן • בתשובה לסמיילי יום ה', 3/8/2006, 17:59
הפניה לערך אחר באנציקלופדיה.
פתחתי ויקיפדיה 400932
עוזי ו. • בתשובה לראובן יום ה', 3/8/2006, 17:59
"p הוא ראשוני שעבורו N הוא שארית ריבועית" = "N הוא שארית ריבועית מודולו p" = "קיים מספר x כך שהשארית של x^2 בחלוקה ל- p היא N".
Now you tell me 400933
ראובן • בתשובה לעוזי ו. יום ה', 3/8/2006, 18:01
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות