Infinite iterator with a faster algorithm (sieves odds-only)

The adding of each discovered prime's incremental step information to the mapping should be postponed until the candidate number reaches the primes square, as it is useless before that point. This drastically reduces the space complexity from O(n/log(n)) to O(sqrt(n/log(n))), in n primes produced, and also lowers the run time complexity due to the use of the hash table based HashMap, which is much more efficient for large ranges.

Sample Code:

// This code is more faster than before

package com.rizvi.so;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

// generates all prime numbers up to about 10 ^ 19 if one can wait 100's of years or so...
// practical range is about 10^14 in a week or so...
public class SoEPagedOdds implements Iterator<Long> {
    private final int BFSZ = 1 << 16;
    private final int BFBTS = BFSZ * 32;
    private final int BFRNG = BFBTS * 2;
    private long bi = -1;
    private long lowi = 0;
    private final ArrayList<Integer> bpa = new ArrayList<>();
    private Iterator<Long> bps;
    private final int[] buf = new int[BFSZ];

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public Long next() {
        if (this.bi < 1) {
            if (this.bi < 0) {
                this.bi = 0;
                return 2L;
            }
            // this.bi muxt be 0
            long nxt = 3 + (this.lowi << 1) + BFRNG;
            if (this.lowi <= 0) { // special culling for first page as no base
                                    // primes yet:
                for (int i = 0, p = 3, sqr = 9; sqr < nxt; i++, p += 2, sqr = p
                        * p)
                    if ((this.buf[i >>> 5] & (1 << (i & 31))) == 0)
                        for (int j = (sqr - 3) >> 1; j < BFBTS; j += p)
                            this.buf[j >>> 5] |= 1 << (j & 31);
            } else { // after the first page:
                for (int i = 0; i < this.buf.length; i++)
                    this.buf[i] = 0; // clear the sieve buffer
                if (this.bpa.isEmpty()) { // if this is the first page after the
                                            // zero one:
                    this.bps = new SoEPagedOdds(); // initialize separate base
                                                    // primes stream:
                    this.bps.next(); // advance past the only even prime of two
                    this.bpa.add(this.bps.next().intValue()); // get the next
                                                                // prime (3 in
                                                                // this case)
                }
                // get enough base primes for the page range...
                for (long p = this.bpa.get(this.bpa.size() - 1), sqr = p * p; sqr < nxt; p = this.bps
                        .next(), this.bpa.add((int) p), sqr = p * p)
                    ;
                for (int i = 0; i < this.bpa.size() - 1; i++) {
                    long p = this.bpa.get(i);
                    long s = (p * p - 3) >>> 1;
                    if (s >= this.lowi) // adjust start index based on page
                                        // lower limit...
                        s -= this.lowi;
                    else {
                        long r = (this.lowi - s) % p;
                        s = (r != 0) ? p - r : 0;
                    }
                    for (int j = (int) s; j < BFBTS; j += p)
                        this.buf[j >>> 5] |= 1 << (j & 31);
                }
            }
        }
        while ((this.bi < BFBTS)
                && ((this.buf[(int) this.bi >>> 5] & (1 << ((int) this.bi & 31))) != 0))
            this.bi++; // find next marker still with prime status
        if (this.bi < BFBTS) // within buffer: output computed prime
            return 3 + ((this.lowi + this.bi++) << 1);
        else { // beyond buffer range: advance buffer
            this.bi = 0;
            this.lowi += BFBTS;
            return this.next(); // and recursively loop
        }
    }

    public static void main(String[] args) {
        long n = 1000000000;
//        long n = 100;
        long strt = System.currentTimeMillis();
        long startTime = System.nanoTime();
        Iterator<Long> gen = new SoEPagedOdds();
        List<Long> primeList = new ArrayList<Long>();
        int count = 0;

//        while (gen.next() <= n) {
//            count++;
//        }
        while (gen.hasNext()) {
            Long val = gen.next();
            if (val <= n) {
                count++;
//                System.out.println("" + val);
            } else {
                break;
            }
        }
        long estimatedTime = System.nanoTime() - startTime;
        System.out.println("TIme taken: " + estimatedTime);
        long elpsd = System.currentTimeMillis() - strt;
        System.out.println("Found " + count + " primes up to " + n + " in "
                + elpsd + " milliseconds.");
    }

    @Override
    public void remove() {
        // TODO Auto-generated method stub

    }

}

Output:

TIme taken: 6836980702
Found 50847534 primes up to 1000000000 in 6838 milliseconds.

Resource Link:

1. https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Java

Sieve of Atkin is faster than Sieve of Eratosthenes

Sample Code:

package com.rizvi.so;

// SieveOfAtkin.java

import java.util.Arrays;

public class SieveOfAtkin {
    private static int limit = 100000000;
    private static boolean[] sieve = new boolean[limit + 1];
    private static int limitSqrt = (int) Math.sqrt((double) limit);

    public static void main(String[] args) {
        // there may be more efficient data structure
        // arrangements than this (there are!) but
        // this is the algorithm in Wikipedia
        // initialize results array
        long startTime = System.nanoTime();
        Arrays.fill(sieve, false);
        // the sieve works only for integers > 3, so
        // set these trivially to their proper values
        sieve[0] = false;
        sieve[1] = false;
        sieve[2] = true;
        sieve[3] = true;

        // loop through all possible integer values for x and y
        // up to the square root of the max prime for the sieve
        // we don't need any larger values for x or y since the
        // max value for x or y will be the square root of n
        // in the quadratics
        // the theorem showed that the quadratics will produce all
        // primes that also satisfy their wheel factorizations, so
        // we can produce the value of n from the quadratic first
        // and then filter n through the wheel quadratic
        // there may be more efficient ways to do this, but this
        // is the design in the Wikipedia article
        // loop through all integers for x and y for calculating
        // the quadratics
        for (int x = 1; x <= limitSqrt; x++) {
            for (int y = 1; y <= limitSqrt; y++) {
                // first quadratic using m = 12 and r in R1 = {r : 1, 5}
                int n = (4 * x * x) + (y * y);
                if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
                    sieve[n] = !sieve[n];
                }
                // second quadratic using m = 12 and r in R2 = {r : 7}
                n = (3 * x * x) + (y * y);
                if (n <= limit && (n % 12 == 7)) {
                    sieve[n] = !sieve[n];
                }
                // third quadratic using m = 12 and r in R3 = {r : 11}
                n = (3 * x * x) - (y * y);
                if (x > y && n <= limit && (n % 12 == 11)) {
                    sieve[n] = !sieve[n];
                }
                    // note that R1 union R2 union R3 is the set R
                    // R = {r : 1, 5, 7, 11}
                    // which is all values 0 < r < 12 where r is
                    // a relative prime of 12
                    // Thus all primes become candidates
            }
        }
            // remove all perfect squares since the quadratic
            // wheel factorization filter removes only some of them
        for (int n = 5; n <= limitSqrt; n++) {
            if (sieve[n]) {
                int x = n * n;
                for (int i = x; i <= limit; i += x) {
                    sieve[i] = false;
                }
            }
        }
            // put the results to the System.out device
            // in 10x10 blocks
        int counter = 0;
        for (int i = 0, j = 0; i <= limit; i++) {
            if (sieve[i]) {
                // System.out.printf("%,8d", i);
                // if (++j % 10 == 0) {
                // System.out.println();
                // } // end if
                // if (j % 100 == 0) {
                // System.out.println();
                // } // end if
                // System.out.println(" " + i);
                counter++;
            }
        }
        System.out.println("Total number of primes:" + counter);
        long estimatedTime = System.nanoTime() - startTime;
        System.out.println("TIme taken: " + estimatedTime);
    }
} // end class SieveOfAtkin

Output:

Total number of primes:5761455
TIme taken: 4343944431

How sieve works? Full procedure

1. http://www.javawithus.com/programs/sieve-of-eratosthenes

Prime Sieve of Eratosthenes: Find all primes smaller than or equal to n.

Sample Code:

package com.rizvi.so;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
// Java program to print all primes smaller than or equal to
// n using Sieve of Eratosthenes

class SieveOfEratosthenes {
    void sieveOfEratosthenes(int n) {
        int counter = 0;
        // Create a boolean array "prime[0..n]" and initialize
        // all entries it as true. A value in prime[i] will
        // finally be false if i is Not a prime, else true.
        boolean prime[] = new boolean[n + 1];
        List<Integer> primeList = new ArrayList<Integer>();
        for (int i = 0; i < n; i++)
            prime[i] = true;

        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed, then it is a prime
            if (prime[p] == true) {
                // Update all multiples of p
                for (int i = p * p; i <= n; i += p) {
                    prime[i] = false;
                }
            }
        }

        // Print all prime numbers
        for (int i = 2; i <= n; i++) {
            if (prime[i] == true) {
//                System.out.println(i + " ");
                primeList.add(i);
                counter++;
            }
        }
        // Show the primes from primeList
//        for(Integer primeVal : primeList) {
//            System.out.println(""+primeVal);
//        }

        System.out.println("Total number of primes: " + counter);
        System.out.println("Total number of primeList: " + primeList.size());
    }

    // Driver Program to test above function
    public static void main(String args[]) {
        Scanner asdf = new Scanner(System.in);
        int n = asdf.nextInt();
        long startTime = System.nanoTime();
        System.out.print("Following are the prime numbers ");
        System.out.println("smaller than or equal to " + n);
        SieveOfEratosthenes g = new SieveOfEratosthenes();
        g.sieveOfEratosthenes(n);
        long estimatedTime = System.nanoTime() - startTime;
        System.out.println();
        System.out.println("Total time taken: " + estimatedTime);
    }
}

// This code has been contributed by Amit Khandelwal.
// http://www.geeksforgeeks.org/sieve-of-eratosthenes/

Output:

100000000
Following are the prime numbers smaller than or equal to 100000000
Total number of primes: 5761455
Total number of primeList: 5761455

Total time taken: 8097239106
 

Prime Number Optimization

Sample Code:

package com.rizvi.so;

import java.util.Scanner;

public class PrimeCheck {

    public static void main(String[] args) {
        Scanner inp = new Scanner(System.in);
        PrimeCheck primeChecker = new PrimeCheck();
        System.out.println("Give Input: ");
        int candidate = inp.nextInt();
        System.out.println(candidate+" is prime: "+primeChecker.isPrime(candidate));
    }

    // checks whether an int is prime or not.
    boolean isPrime(int n) {
        // check if n is 2
        if (n == 2)
            return true;
        // check if n is a multiple of 2
        if (n < 2 || n % 2 == 0)
            return false;
        // if not, then just check the odds
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
}

Output:

Give Input:
31
31 is prime: true

Resource Link:

1. http://introcs.cs.princeton.edu/java/14array/PrimeSieve.java.html

Gtk-WARNING **: cannot open display: xhost+ : How to Fix “Cannot Open Display” Error While Launching GUI on Remote Server

Question: When I try to launch any GUI application on a remote server, I’m getting the “cannot open display:” error, as shown below. How do I fix this?

For example, while launching the gedit on remote server, I got the following message.

(gedit:3658): Gtk-WARNING **: cannot open display: 

I get similar message when I try to open any GUI application. For example, launching Oracle Installer on remote server also gives the “cannot open display” error.

Answer: You can fix the “cannot open display” error by following the xhost procedure mentioned in this article.

1. Allow clients to connect from any host using xhost+

Execute the following command to disable the access control, by which you can allow clients to connect from any host.

$ xhost +
access control disabled, clients can connect from any host

2. Enable X11 forwarding

While doing ssh use the option -X to enable X11 forwarding.

$ ssh username@hostname -X

Enable trusted X11 forwarding, by using the -Y option,

$ ssh username@hostname -Y

3. Open GUI applications in that host

After opening ssh connection to the remote host as explained above, you can open any GUI application which will open it without any issue.

If you still get the “cannot open display” error, set the DISPLAY variable as shown below.

$ export DISPLAY='IP:0.0'

Note: IP is the local workstation’s IP where you want the GUI application to be displayed.

Console/Command prompt output and error log write to a specific file

Output and error log write to a specific file.

 '>' will overwrite the file, '>>' will append to the file

Overwriting and appending output file
======================================

'>'  : for overwriting output file.
'>>' : for appending to the same logfile.



Overwriting and appending error log file
========================================

'2>' : for overwriting error log file.
'2>>': for appending to the same error logfile


java -jar test.jar > output.log

java -jar test.jar >> output.log

java -jar test.jar 2> error.log

java -jar test.jar 2>> error.log

Debug class file with source code in Eclipse

Eclipse Class Decompiler is one of them.

How to run a jar file in command prompt?

First Solution

java -jar <myJar>.jar

Second Solution(Jon Skeet): 

You need to specify a Main-Class in the jar file manifest.
Oracle's tutorial contains a complete demonstration, but here's another one from scratch. You need two files:
Test.java:

public class Test
{
    public static void main(String[] args)
    {
        System.out.println("Hello world");
    }
}

manifest.mf:

Manifest-version: 1.0
Main-Class: Test

Note that the text file must end with a new line or carriage return. The last line will not be parsed properly if it does not end with a new line or carriage return.
Then run:

javac Test.java
jar cfm test.jar manifest.mf Test.class
java -jar test.jar

Output:

Hello world

Resource Link:

1. http://stackoverflow.com/questions/5774970/run-jar-file-in-command-prompt
2. http://stackoverflow.com/questions/1238145/how-to-run-a-jar-file

Algorithm Study

1. https://sites.google.com/site/indy256/algo/arrangements
2. https://www.quora.com/Are-there-any-good-sites-for-learning-algorithm-programming-concepts-every-day-similar-to-the-SAT-question-of-the-day
3. http://www.ideserve.co.in/learn/nth-fibonacci-number#algorithmVisualization
4. https://www.quora.com/What-are-the-best-websites-with-algorithm-practice-problems
5. http://introcs.cs.princeton.edu/java/14array/
6. http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L11-InsSort.htm
7. https://www.dyclassroom.com/sorting-algorithm/merge-sort

Auto Scale DynamoDB With Dynamic DynamoDB

1. https://aws.amazon.com/blogs/aws/auto-scale-dynamodb-with-dynamic-dynamodb/
2. https://raw.githubusercontent.com/sebdah/dynamic-dynamodb/master/cloudformation-templates/dynamic-dynamodb.json

Cron Job Study

To see what crontabs are currently running on your system, you can open a terminal and run:

$ sudo crontab -l

To edit the list of cronjobs you can run:

$ sudo crontab -e

Storing the crontab output
==========================
By default cron saves the output of /bin/execute/this/script.sh in the user's mailbox (root in this case). But it's prettier if the output is saved in a separate logfile. Here's how:

*/10 * * * * /bin/execute/this/script.sh >> /var/log/script_output.log 2>&1

Explained
==========
Linux can report on different levels. There's standard output (STDOUT) and standard errors (STDERR). STDOUT is marked 1, STDERR is marked 2. So the following statement tells Linux to store STDERR in STDOUT as well, creating one datastream for messages & errors:

2>&1

Now that we have 1 output stream, we can pour it into a file. Where > will overwrite the file, >> will append to the file. In this case we'd like to to append:

>> /var/log/script_output.log

Mailing the crontab output
==========================
By default cron saves the output in the user's mailbox (root in this case) on the local system. But you can also configure crontab to forward all output to a real email address by starting your crontab with the following line:

MAILTO="yourname@yourdomain.com"

Mailing the crontab output of just one cronjob
==============================================
If you'd rather receive only one cronjob's output in your mail, make sure this package is installed:

$ aptitude install mailx

And change the cronjob like this:

*/10 * * * * /bin/execute/this/script.sh 2>&1 | mail -s "Cronjob ouput" yourname@yourdomain.com

Trashing the crontab output
============================
Now that's easy:

*/10 * * * * /bin/execute/this/script.sh > /dev/null 2>&1

Just pipe all the output to the null device, also known as the black hole. On Unix-like operating systems, /dev/null is a special file that discards all data written to it.

Resource Link: http://kvz.io/blog/2007/07/29/schedule-tasks-on-linux-using-crontab/

Cron Job Generator Tool: http://www.crontab-generator.org/

1. http://www.corntab.com/popular_crontabs
2. https://github.com/lathonez/dotfiles/blob/master/crontab/example.crontab
3. http://www.dba-oracle.com/linux/scheduling_with_crontab.htm
4. https://www.debian-tutorials.com/crontab-tutorial-cron-howto
5. http://stackoverflow.com/questions/18945669/linux-how-to-run-script-at-certain-time

DynamoDB Local for Desktop Development

1. https://aws.amazon.com/blogs/aws/dynamodb-local-for-desktop-development/

How to change read/write capacity in AWS DynamoDB?

Hi,

Yes, it is very easy to automate changes to DynamoDB capacity. This can be done via the CLI or any of the SDKs.

A few caveats:
1: You can increase capacity on a table an unlimited number of times per day, but you can only reduce capacity on that table 4x a day
2: Once you increase capacity, you're paying for that capacity for an hour. There's no saving to be had by trying to ramp capacity up and down in real time.

One way to automate scaling is with the Dynamic DynamoDB script, a third party tool that will ramp your capacity up and down based upon actual load. We have a blog article posted describing it's use.

That may be overkill for your situation. If you just want to turn capacity up during business hours to a fixed level, and then turn it down to lower level after hours, you can do that with a simple shell script. If you have a persistent EC2 instance running you can simply add these scripts to the crontab on that box, or run the AWC CLI command from Data Pipeline with a ShellCommandActivity (we provide a template for doing this).

If you're doing it in a shell script, it might look something like:

#!/bin/bash
TABLE="my_ddb_table"
WCU=50
RCU=50
aws dynamodb update-table --table-name $TABLE \
  --provisioned-throughput {"ReadCapacityUnits":$RCU ,"WriteCapacityUnits":$WCU }

The simplest solution would be to have one version to run in the morning and another for the evening.

Resource Link:

1. https://forums.aws.amazon.com/thread.jspa?messageID=725985                 

Eight ways to lower your DynamoDB costs

1. https://blog.cloudability.com/eight-ways-to-lower-your-dynamodb-costs/
2. https://blog.cloudability.com/saved-64-devtest-instances-scheduling-uptime/

Cost optimization using AWS

1. https://d0.awsstatic.com/whitepapers/Cost_Optimization_with_AWS.pdf

Provisioned throughput calculation

1. https://medium.com/devoops-and-universe/database-performance-aws-vs-bare-metal-452f64481b07#.4a1gg4y5b

memcached vs. Ehcache

1. http://vschart.com/compare/memcached/vs/ehcache
2. http://gregluck.com/blog/archives/2007/05/comparing-memcached-and-ehcache-performance/
3. http://stackoverflow.com/questions/14029366/hibernate-ehcache-vs-memcache