שאלה לגבי יעילות

[naring]

שאלה לגבי יעילות

שלום אני חדש פה, מקווה שתוכלו לעזור לי. בניתי תוכנה בפסקל למציאת מספרים מושלמים (מספר מושלם= מספר שכל המחלקים שלו ללא שארית ביחד שווים למשפר עצמו. למשל, 6 מתחלק ב1, ב2, וב3 (את המס' עצמו לא סופרים) ו1+2+3 שווה ביחד ל-6). זה הולך ככה פחות או יותר (ראו קובץ מצורף, אני לא מצליח לעשות את זה מיושר לשמאל וששאר ההודעה תהיה מיושרת לימין) עכשיו הבעיה היא היעילות. בגלל שהתוכנה צריכה להריץ סיגמה מיליארד בריבוע מספרים, זה לוקח הרבה זמן. האם לדעתכם אני יכול לקצר את זמן ריצת התוכנית? האם אני פשוט צריך לעשות את אותו דבר באסמבלר? להריץ את זה מהדוס? לייעל את הזיכרון? תודה לכם

 

[vinney]

זה לא משנה

לא משנה באיזו שפה אתה עושה את זה, משנה האלגוריתם. אם אני לא טועה, זאת בעיית NPC, לכן לא תוכל לשפר בהרבה

 

[naring]

מה, אז המיתוס הזה שאסמבלי מקצר את

זמן הריצה - שגוי?

 

[vinney]

לא, בכלל לא

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

 

[IP yuval]

כפי שאתה יכול לקרוא פה:

http://en.wikipedia.org/wiki/Perfect_number עד 10 בחזקת 300, כל המספרים המשולשמים זוגיים, והוכח שאפשר למצוא אותם בעזרת נוסחה...

 

[vinney]

לא כל המספרים המושלים

כל מספר שהוא אחד פחות מספר מרסן יהיה מושלם, אבל זה חד כיווני, זה דו כיווני לכל מספר מושלם זוגי. לא ידוע (כפי שכתוב שם) אם יש מספרים מושלמים אי זוגיים. שים לב שמניית המספרים המושלמים (כמו גם, מספרי מרסן) היא NPC.

 

[אלוהים1980]

לטובת הידע הכללי: מה זה מספר מרסן?

 

[vinney]

תסתכל בקישור שהוא שם

כתוב שם בפירוט, גם יש להם מאמר לא קטן על מספרי מרסן לכשעצמם. עקרונית מדובר במספר ראשוני הקטן באחד מחזקה ראשונית כלשהי של 2. למשל, 7 הוא מספר מרסן משום ש2 בחזקת 3 פחות 1 נותן 7.

 

[naring]

אוקיי. תודה לכם.../images/Emo51.gif