जावास्क्रिप्ट में एरेटोस्टेनेस एल्गोरिदम की चलनी बड़ी संख्या

Question

के लिए अंतहीन चल रही है। मैं जावास्क्रिप्ट में Sieve of Eratosthenes एल्गोरिदम लिखने की कोशिश कर रहा हूं। असल में मैं सिर्फ सचमुच नीचे दिए गए चरणों का पालन किया:

1. 2 से लगातार पूर्णांकों की एक सूची बनाएं (n-1)
2. चलो पहले प्रधानमंत्री संख्या पी बराबर 2
3. पी से शुरू, ऊपर बढ़ते हुए क्रम में गिनती पी और निकालता है इन नंबरों (पी और पी के गुणज)
4. सूची में अगले नंबर पर जाएं और से प्रत्येक को दोहराने 2,3,4
5. अनजाने सूची

करने के लिए पुन: शामिल करें रूढ़ अंक नष्ट कर दिया

function eratosthenes(n){ 
var array = []; 
var tmpArray = []; // for containing unintentionally deleted elements like 2,3,5,7,... 
var maxPrimeFactor = 0; 
var upperLimit = Math.sqrt(n); 
var output = []; 

// Eratosthenes algorithm to find all primes under n 

// Make an array from 2 to (n - 1) 
//used as a base array to delete composite number from 
for(var i = 2; i < n; i++){ 
    array.push(i); 
} 

// Remove multiples of primes starting from 2, 3, 5,... 
for(var i = array[0]; i < upperLimit; i = array[0]){ 
    removeMultiples: 
    for(var j = i, k = i; j < n; j += i){ 
     var index = array.indexOf(j); 
     if(index === -1) 
      continue removeMultiples; 
     else 
      array.splice(index,1); 
    } 
    tmpArray.push(k); 
} 
array.unshift(tmpArray); 
return array; 
} 

यह छोटी संख्या के लिए काम करता है लेकिन एक लाख से भी बड़ा संख्या के लिए नहीं:

और यह है कि क्या मैं के साथ आए हैं है। मैंने परीक्षण करने के लिए Node.js का उपयोग किया और प्रक्रिया केवल अंतहीन लगती है और कोई स्मृति त्रुटि दिखाई नहीं दे रही है। मैंने एक समाधान here (जावास्क्रिप्ट में भी) पढ़ा है लेकिन अभी भी इसे पूरी तरह से समझ नहीं सकता है।

प्रश्न: इस काम को पर्याप्त रूप से बड़ी संख्या में एक लाख और उससे अधिक के लिए कैसे बनाया जाए?

Answer 1

आप Array#indexOf और Array#splice जैसे सरणी हेरफेर फ़ंक्शन का उपयोग करके जानबूझकर धीमी गति से एरोटोस्टेनेस की चाकू बना रहे हैं जो रैखिक समय में चलता है। जब आप दोनों परिचालनों के लिए ओ (1) प्राप्त कर सकते हैं।

var eratosthenes = function(n) { 
    // Eratosthenes algorithm to find all primes under n 
    var array = [], upperLimit = Math.sqrt(n), output = []; 

    // Make an array from 2 to (n - 1) 
    for (var i = 0; i < n; i++) { 
     array.push(true); 
    } 

    // Remove multiples of primes starting from 2, 3, 5,... 
    for (var i = 2; i <= upperLimit; i++) { 
     if (array[i]) { 
      for (var j = i * i; j < n; j += i) { 
       array[j] = false; 
      } 
     } 
    } 

    // All array[i] set to true are primes 
    for (var i = 2; i < n; i++) { 
     if(array[i]) { 
      output.push(i); 
     } 
    } 

    return output; 
}; 

You can see a live example for n = 1 000 000 here.

Answer 2

यह सवाल क्या एक "बड़ी संख्या" है और स्वीकार करता है की परिभाषा में कम पक्ष पर एक छोटे से कंजूस है:

नीचे एरेटोस्थेनेज की चलनी पारंपरिक प्रोग्रामिंग प्रथाओं पीछा कर रहा है कि यह केवल दस लाख से शुरू होता है, जिसके लिए current answer काम करता है; हालांकि, यह प्रत्येक तत्व के लिए एक 8-बाइट संख्या (64 बिट्स की एक डबल वास्तविकता) के रूप में काफी स्मृति का उपयोग करता है और प्रत्येक पाए गए प्राइम के लिए 8-बाइट संख्या। यह उत्तर 250 मिलियन और उससे अधिक के बारे में "बड़ी संख्या" के लिए काम नहीं करेगा क्योंकि यह जावास्क्रिप्ट निष्पादन मशीन के लिए उपलब्ध स्मृति की मात्रा से अधिक होगा।

निम्नलिखित जावास्क्रिप्ट कोड "अनंत" (असंबद्ध) को लागू करने वाला पृष्ठ जावा सेगेटेड इरेटोस्टेनेस की चलती चलनी उस समस्या से अधिक है कि इसमें केवल एक बिट-पैक 16 किलोबाइट पेज सेगमेंटेड सेविंग बफर (एक बिट एक संभावित प्राइम नंबर का प्रतिनिधित्व करता है) का उपयोग करता है और केवल वर्तमान पृष्ठ खंड में वर्तमान उच्चतम संख्या के वर्ग रूट तक आधार प्राइम्स के लिए भंडारण का उपयोग करता है, बिना किसी भंडारण की आवश्यकता के क्रम में वास्तविक पाए गए प्राइम; यह भी केवल केवल भी प्रधानमंत्री के रूप में अजीब कंपोजिट sieving द्वारा समय की बचत 2:

var SoEPgClass = (function() { 
    function SoEPgClass() { 
    this.bi = -1; // constructor resets the enumeration to start... 
    } 
    SoEPgClass.prototype.next = function() { 
    if (this.bi < 1) { 
     if (this.bi < 0) { 
     this.bi++; 
     this.lowi = 0; // other initialization done here... 
     this.bpa = []; 
     return 2; 
     } else { // bi must be zero: 
     var nxt = 3 + 2 * this.lowi + 262144; //just beyond the current page 
     this.buf = []; 
     for (var i = 0; i < 2048; i++) this.buf.push(0); // faster initialization 16 KByte's: 
     if (this.lowi <= 0) { // special culling for first page as no base primes yet: 
      for (var i = 0, p = 3, sqr = 9; sqr < nxt; i++, p += 2, sqr = p * p) 
      if ((this.buf[i >> 5] & (1 << (i & 31))) === 0) 
       for (var j = (sqr - 3) >> 1; j < 131072; j += p) 
       this.buf[j >> 5] |= 1 << (j & 31); 
     } else { // other than the first "zeroth" page: 
      if (!this.bpa.length) { // if this is the first page after the zero one: 
      this.bps = new SoEPgClass(); // initialize separate base primes stream: 
      this.bps.next(); // advance past the only even prime of 2 
      this.bpa.push(this.bps.next()); // keep the next prime (3 in this case) 
      } 
      // get enough base primes for the page range... 
      for (var p = this.bpa[this.bpa.length - 1], sqr = p * p; sqr < nxt; 
      p = this.bps.next(), this.bpa.push(p), sqr = p * p); 
      for (var i = 0; i < this.bpa.length; i++) { //for each base prime in the array 
      var p = this.bpa[i]; 
      var s = (p * p - 3) >> 1; //compute the start index of the prime squared 
      if (s >= this.lowi) // adjust start index based on page lower limit... 
       s -= this.lowi; 
      else { //for the case where this isn't the first prime squared instance 
       var r = (this.lowi - s) % p; 
       s = (r != 0) ? p - r : 0; 
      } 
      //inner tight composite culling loop for given prime number across page 
      for (var j = s; j < 131072; j += p) this.buf[j >> 5] |= 1 << (j & 31); 
      } 
     } 
     } 
    } 
    //find next marker still with prime status 
    while (this.bi < 131072 && this.buf[this.bi >> 5] & (1 << (this.bi & 31))) .bi++; 
    if (this.bi < 131072) // within buffer: output computed prime 
     return 3 + ((this.lowi + this.bi++) * 2); 
    else { // beyond buffer range: advance buffer 
     this.bi = 0; 
     this.lowi += 131072; 
     return this.next(); // and recursively loop just once to make a new page buffer 
    } 
    }; 
    return SoEPgClass; 
})(); 

ऊपर कोड निम्नलिखित JavaScript कोड द्वारा दिए गए सीमा तक अभाज्य संख्या की गणना करने के लिए उपयोग किया जा सकता है:

window.onload = function() { 
    var elpsd = -new Date().getTime(); 
    var top_num = 1000000000; 
    var cnt = 0; 
    var gen = new SoEPgClass(); 
    while (gen.next() <= top_num) cnt++; 
    elpsd += (new Date()).getTime(); 
    document.getElementById('content') 
    .innerText = 'Found ' + cnt + ' primes up to ' + top_num + ' in ' + elpsd + ' milliseconds.'; 
}; 

यदि जावास्क्रिप्ट कोड के उपरोक्त दो टुकड़े उसी फ़ोल्डर में app.js नामक फ़ाइल में डाल दिए गए हैं, तो निम्न HTML कोड जो कुछ भी नामित है।जब एक JavaScript निष्पादन इंजन पर चलने

<!DOCTYPE html> 

<html lang="en"> 
    <head> 
    <meta charset="utf-8" /> 
    <title>Page Segmented Sieve of Eratosthenes in JavaScript</title> 
    <script src="app.js"></script> 
    </head> 
    <body> 
    <h1>Page Segmented Sieve of Eratosthenes in JavaScript.</h1> 

    <div id="content"></div> 
    </body> 
</html> 

इस कोड को एक अरब श्रृंखला के लिए चलनी सकता है कुछ 10 सेकंड के: एचटीएमएल, आप इसे में HTML फ़ाइल खोलने के द्वारा आपके ब्राउज़र में कोड को चलाने के लिए सक्षम हो जाएगा Google क्रोम के वी 8 इंजन जैसे जस्ट-इन-टाइम (जेआईटी) संकलन का उपयोग करना। चरम व्हील फैक्टरलाइजेशन और सबसे कम आधार प्राइम्स के पेज बफर के प्री-कूलिंग का उपयोग करके और लाभ प्राप्त किए जा सकते हैं, इस मामले में किए गए काम की मात्रा चार के आगे के कारक द्वारा काटा जा सकता है, जिसका अर्थ है कि प्राइम की संख्या गिना जा सकता है कुछ सेकंड में एक बिलियन तक (गिनती के लिए उपयोग की जाने वाली गणना की आवश्यकता नहीं होती है बल्कि पेज सेगमेंट बफर पर सीधे बिट गिनती टेबल का उपयोग कर सकते हैं), हालांकि कोड की जटिलता की लागत पर।

Answer 3

बस इसके मजे के लिए, मैंने एडीस्टोटेन चलनी एल्गोरिदम (नोड के साथ चलाया) को सख्ती से टीडीडी के नियमों का पालन करने के लिए लागू किया। साक्षात्कार के लिए यह संस्करण पर्याप्त होना चाहिए, एक स्कूल अभ्यास के रूप में या बस जैसा था - थोड़ा सा गड़बड़ाना।

मुझे बताएं, कि मुझे निश्चित रूप से लगता है कि स्वीकार किया गया जवाब गॉर्डनबूड द्वारा प्रदान किया जाना चाहिए।

module.exports.compute = function(size) 
{ 
    if (!utils.isPositiveInteger(size)) 
    { 
     throw new TypeError("Input must be a positive integer"); 
    } 

    console.time('optimal'); 
    console.log(); 
    console.log("Starting for optimal computation where size = " + size); 
    let sieve = utils.generateArraySeq(2, size); 

    let prime = 2; 
    while (prime) 
    { 
     // mark multiples 
     for (let i = 0; i < sieve.length; i += prime) 
     { 
      if (sieve[i] !== prime) 
      { 
       sieve[i] = -1; 
      } 
     } 

     let old_prime = prime; 
     // find next prime number 
     for (let i = 0; i < sieve.length; i++) 
     { 
      if ((sieve[i] !== -1) && (sieve[i] > prime)) 
      { 
       prime = sieve[i]; 
       break; 
      } 
     } 

     if (old_prime === prime) 
     { 
      break; 
     } 
    } 
    console.timeEnd('optimal'); 
    // remove marked elements from the array 
    return sieve.filter( 
     function(element) 
     { 
      return element !== -1; 
     }); 
} // compute 

मैं किसी भी समझदार आलोचना की सराहना करता हूं।

The whole repository can be found on my github account.

Answer 4

मैं अलेक्जेंडर के लिए एक टिप्पणी के रूप में पोस्ट करेंगे, लेकिन मैं प्रतिष्ठा है कि ऐसा करने के लिए नहीं है। उसका जवाब कमाल है, और यह इसे तेजी से बनाने के लिए बस इसे बदल देता है। मैं एन = 100,000,000 परीक्षण करके बेंचमार्क किया।

'सरणी' में सही और गलत उपयोग करने के बजाय, मुझे 1 और 0 का उपयोग करके एक बड़ी गति वृद्धि मिलती है। यह क्रोम में 5000 एमएस से 4250 एमएस तक अपना समय कम कर देता है। फ़ायरफ़ॉक्स अप्रभावित था (5600 एमएस या तो रास्ता)।

फिर हम यह ध्यान में रख सकते हैं कि संख्याएं कभी भी प्रमुख नहीं होंगी। बल्ले से 2 'आउटपुट' में रखें और आप i = 3 कर सकते हैं; i + = 2, और j + = i * 2 चलनी के दौरान (हम भी गुणांक को छोड़ सकते हैं क्योंकि किसी भी संख्या से भी संख्या भी होती है), जब तक हम भी i + = 2 पर 'आउटपुट' पर दबाव डालते समय समाप्त। इससे क्रोम में 4250 एमएस से 3350 एमएस तक मेरा समय कम हो गया। फ़ायरफ़ॉक्स को थोड़ा कम लाभ हुआ, 5600 एमएस से 4800 एमएस तक गिर गया।

वैसे भी, उन दो tweaks के संयोजन ने मुझे क्रोम में 33% गति बढ़ावा दिया, और फ़ायरफ़ॉक्स में 14% बढ़ावा दिया। अलेक्जेंडर के कोड का बेहतर संस्करण यहां दिया गया है।

var eratosthenes = function(n) { 
    // Eratosthenes algorithm to find all primes under n 
    var array = [], upperLimit = Math.sqrt(n), output = [2]; 

    // Make an array from 2 to (n - 1) 
    for (var i = 0; i < n; i++) 
     array.push(1); 

    // Remove multiples of primes starting from 2, 3, 5,... 
    for (var i = 3; i <= upperLimit; i += 2) { 
     if (array[i]) { 
      for (var j = i * i; j < n; j += i*2) 
       array[j] = 0; 
     } 
    } 

    // All array[i] set to 1 (true) are primes 
    for (var i = 3; i < n; i += 2) { 
     if(array[i]) { 
      output.push(i); 
     } 
    } 

    return output; 
};