Saturday, August 12, 2023

Nifty Info on 123456789 Factorial

The answers provided in the questions were collected using:

  • Default eclipse 2023-06 IDE for Mac
  • No special java vm args
  • jdk 1.8
  • Mac Studio M1 (10 core)

Question : How many digits are there in 123456789 factorial?

Answer : 260,959,261 digits.

Question : How long does it take to compute 123456789 factorial?

  • Answer 1 : Using prime sieve method, it takes 28,244,345 ms.
  • Answer 2 : Using recursive method, StackOverflowError.

Question : If the result of 123456789 factorial was written to a plain text file, how big will it be?

Answer : 263.6 MB.

Here's the full java code:

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class FactorialUsingPrimeSieveMethod {

    private int findExponent(int input, int prime) {
        int q = input, m = 0;
        if (prime > input) {
            return 0;
        }
        if (prime > input / 2) {
            return 1;
        }
        while (q >= prime) {
            q /= prime;
            m += q;
        }
        return m;
    }

    private boolean[] initializeSieve(int input) {
        boolean sieve[] = new boolean[input + 1];
        Arrays.fill(sieve, true);

        for (int p = 2; p * p <= input; p++) {
            if (sieve[p] == true) {
                for (int i = p * p; i <= input; i += p) {
                    sieve[i] = false;
                }
            }
        }

        return sieve;
    }

    private int[] selectPrimeNumbers(int input) {
        ArrayList<Integer> primeTable = new ArrayList<Integer>();
        boolean sieve[] = initializeSieve(input);
        for (int i = 2; i <= input; i++) {
            if (sieve[i] == true) {
                primeTable.add(i);
            }
        }

        return primeTable.stream().mapToInt(i -> i).toArray();

    }

    private int[] generateExponentTable(int input, int[] primeTable) {
        ArrayList<Integer> exponentTable = new ArrayList<Integer>();
        for (int prime : primeTable) {
            exponentTable.add(Integer.valueOf(findExponent(input, prime)));
        }

        return exponentTable.stream().mapToInt(i -> i).toArray();

    }

    private LinkedList<BigInteger> runParallelExponentiation(int[] primeTable, int[] exponentTable) {
        int proc = Runtime.getRuntime().availableProcessors();
        ExecutorService executorService = Executors.newFixedThreadPool(proc);

        List<Future<BigInteger>> futureList = new ArrayList<Future<BigInteger>>();
        LinkedList<BigInteger> intermediate = new LinkedList<BigInteger>();

        for (int i = 0; i < primeTable.length; i++) {
            Callable<BigInteger> worker = new PrimeSieveExponentiationWrapper(primeTable[i], exponentTable[i]);
            Future<BigInteger> submit = executorService.submit(worker);
            futureList.add(submit);
        }

        for (Future<BigInteger> future : futureList) {
            try {
                intermediate.add(future.get());
            } catch (InterruptedException e) {
                e.printStackTrace();
            } catch (ExecutionException e) {
                e.printStackTrace();
            }
        }

        executorService.shutdown();
        return intermediate;
    }

    private synchronized BigInteger runParallelMultiplication(LinkedList<BigInteger> intermediate) {
        BigInteger one = BigInteger.ONE;
        int proc = Runtime.getRuntime().availableProcessors();
        ExecutorService executorService = Executors.newFixedThreadPool(proc);

        final LinkedList<BigInteger> roundaboutList = intermediate;

        while (roundaboutList.size() != 1) {
            System.out.println(" Current size = " + roundaboutList.size());
            BigInteger x = intermediate.pollLast();
            System.out.println(" Size after first poll = " + roundaboutList.size());
            BigInteger y = intermediate.pollLast();
            System.out.println(" Size after second poll = " + roundaboutList.size());
            Callable<BigInteger> worker = new PrimeSieveMultiplicationWrapper(x, y);
            Future<BigInteger> submit = executorService.submit(worker);
            try {
                roundaboutList.addFirst(submit.get());
            } catch (InterruptedException e) {
                e.printStackTrace();
            } catch (ExecutionException e) {
                e.printStackTrace();
            }
        }

        executorService.shutdown();
        return one.multiply(roundaboutList.getFirst());
    }

    private BigInteger factorial(int input) {
        BigInteger result = BigInteger.ONE;
        int[] primeTable = selectPrimeNumbers(input);
        int[] exponentTable = generateExponentTable(input, primeTable);

        final LinkedList<BigInteger> intermediate = runParallelExponentiation(primeTable, exponentTable);
        BigInteger product = runParallelMultiplication(intermediate);
        return result.multiply(product);
    }

    private void exportToFile(BigInteger result, int n) {
        String toParse = result.toString();
        String parsedResult = toParse.replaceAll("(.{100})", "$1\n");
        String path = System.getProperty("user.home") + File.separator + "results" + File.separator + String.valueOf(n)
                + ".txt";

        try {
            File fileName = new File(path);
            if (!fileName.exists()) {
                fileName.getParentFile().mkdirs();
                fileName.createNewFile();
            }
            FileWriter writer = new FileWriter(fileName);
            writer.write(parsedResult);
            writer.flush();
            writer.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void recordExecTime(FactorialUsingPrimeSieveMethod calculator, int n) {
        long startTime = System.currentTimeMillis();
        BigInteger result = calculator.factorial(n);
        long endTime = System.currentTimeMillis();
        System.out.println(n + "! took " + (endTime - startTime) + " ms using prime sieve method. Result has = "
                + result.toString().length() + " digits");
        //exportToFile(result, n);
    }

    public static void main(String[] args) {
        FactorialUsingPrimeSieveMethod calculator = new FactorialUsingPrimeSieveMethod();
        calculator.recordExecTime(calculator, 12345);
        calculator.recordExecTime(calculator, 123456);
        calculator.recordExecTime(calculator, 1234567);
        calculator.recordExecTime(calculator, 12345678);
        calculator.recordExecTime(calculator, 123456789);
    }

    class PrimeSieveExponentiationWrapper implements Callable<BigInteger> {

        int prime;
        int exponent;

        public PrimeSieveExponentiationWrapper(int prime, int exponent) {
            this.prime = prime;
            this.exponent = exponent;
        }

        @Override
        public BigInteger call() throws Exception {
            // System.out.println(" Calculating " + prime + " ^ " + exponent);
            return BigInteger.valueOf(prime).pow(exponent);
        }
    }

    class PrimeSieveMultiplicationWrapper implements Callable<BigInteger> {

        private BigInteger x;
        private BigInteger y;

        PrimeSieveMultiplicationWrapper(BigInteger x, BigInteger y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public BigInteger call() throws Exception {
            if (x == null) {
                if (y == null) {
                    return BigInteger.ONE;
                } else {
                    return y;
                }
            }
            return x.multiply(y);
        }
    }
}


Monday, March 29, 2021

El Capitan, My El Capitan

I wanted to re-install El Capitan on my very old MacBook Pro. It had 2 disk partitions which I wanted to merge but couldn't do so via Disk Utility while in recovery mode. It won't start-up recovery mode via internet with Command + Option + R. 

My scouring over the world wide web ended in me having to:

  • Download the dmg file from Apple.
  • Run below commands in Big Sur (or any macos which has higher version than El Capitan) to create the installation media (using a 32GB flash drive):
    • rm -rf /tmp/El\ Capitan
    • pkgutil --expand /Volumes/Install\ OS\ X/InstallMacOSX.pkg /tmp/El\ Capitan
    • diskutil eject Install\ OS\ X
    • cd /tmp/El\ Capitan
    • hdiutil attach InstallMacOSX.pkg/InstallESD.dmg -noverify -nobrowse -mountpoint /Volumes/esd
    • sudo asr restore -source /Volumes/esd/BaseSystem.dmg -target /Volumes/MyVolume -noprompt -noverify -erase
    • diskutil rename /Volumes/OS\ X\ Base\ System /Volumes/Install\ El\ Capitan
    • rm /Volumes/Install\ El\ Capitan/System/Installation/Packages
    • cp -rp /Volumes/esd/Packages /Volumes/Install\ El\ Capitan/System/Installation
    • cp -rp /Volumes/esd/BaseSystem.chunklist /Volumes/Install\ El\ Capitan/
    • cp -rp /Volumes/esd/BaseSystem.dmg /Volumes/Install\ El\ Capitan/
    • hdiutil detach /Volumes/esd
    • sudo bless --folder /Volumes/Install\ El\ Capitan/System/Library/CoreServices --label Install\ El\ Capitan
    • cp /Volumes/Install\ El\ Capitan/Install\ OS\ X\ El\ Capitan.app/Contents/Resources/InstallAssistant.icns /Volumes/Install\ El\ Capitan/.VolumeIcon.icns
    • cd "$HOME"
    • rm -r /tmp/El\ Capitan
    • diskutil eject /Volumes/Install\ El\ Capitan

 

 

Sunday, May 3, 2020

COVID-19 Work From Home

The current firm I work for has transitioned most tech and ops people from using physical PCs to using LVDI. In the office, I have 4 x 24" monitors with pixel density 1980 x 1080 attached to a thin client that displays my LVDI desktop. Signing-on is easy because the network is internal. There's also a link to sign-on externally in case there's a need to quickly check something.

Both of these methods only require:
  • browser 
  • Citrix
At home, I have a gaming PC with 1 x 27" monitor with density more than 1980 x 1080 (although the graphics card can display 3 x 4k). There's also an extra 1980 x 1080 24" monitor attached to a very old mac mini.

To make employees work comfortably from home, my firm allowed purchasing of peripherals but only for max USD 150 on a monitor. The best I can get with the amount is 1 x 27" monitor with 1980 x 1080. 

I can now at least have dual monitor on my gaming PC to display my LVDI desktop. 

However, due to differences in pixel density, I always have to scale the gaming monitor down to 1980 x 1080 so that Citrix can be displayed on both monitors. Furthermore, since it's a gaming PC, I don't really need the extra graphics power and carbon footprint on electricity usage (which I have to handle as personal expense).

When COVID-19 struck, non-essential people were required to work from home. While the pandemic is going to stay here for a while, it is now very challenging and cumbersome to set-up my PC every time I login.

The thinking light bulb turned on when a colleague mentioned that Raspberry Pi 4 can display 2 x 4k. This set-up will allow me to have dual monitors using the old 24" and the new 27" monitor which have the same pixel density. I can now leave my gaming PC at peace (meaning the wife can use it too by playing World of Warcraft while I am working).

The problems I faced (in sequence):
  1. Citrix ica isn't recognized
  2. Citirx ica doesn't auto launch
  3. digital certificate issues
  4. Citrix can't span both monitors when the app is maximized
  5. middle click doesn't work as expected
None of the solutions are mine to take credit for. These were all gathered from all over the internet but succinctly presented below.

To solve (1):
  • download the debian package "Citrix Workspace app for Linux (ARM HF)"
  • cd /home/pi/Downloads
  • issue command sudo dpkg -i icaclient*.deb
To solve (2):
  • once the ica is downloaded in Chromium, set to "Always Open"
To solve (3):
  • the error dialog will tell you which certificate to download from the issuer (DigiTrust, EnTrust, etc)
  • if the certificate needs some conversion you'll have to install openssl and convert with proper command
  • sudo copy the pem file to /opt/Citrix/ICAClient/keystore/cacerts
  • execute command /opt/Citrix/ICAClient/util/ctx_rehash
To solve (4):
  • install icewm window manager by issuing command sudo apt-get install icewm
  • edit the files /etc/xdg/lxsession/LXDE/desktop.conf and /etc/xdg/lxsession/LXDE-pi/desktop.conf by changing from window_manager=openbox-lxde-pi to window_manager=icewm
  • edit /usr/share/icewm/preferences with ShowTaskBar=0
  • execute command sudo reboot
To solve (5):
  • edit /home/pi/.ICAClient/wfclient.ini with MouseSendsControlV=False
Now, I have an energy efficient very very thin client with 2 monitors that can display my LVDI desktop during the COVID-19 pandemic!

Friday, July 19, 2019

Creating a RAID5 NAS with My Raspberry Pi 2B

My Raspberry Pi 2B has been unused since I bought it in 2015. 

After 4 years, I have also accumulated 3 x 2TB external SATA HDDs (2 of which are from someone who has moved on to using cloud storage, and 1 from my Alienware Aurora R5).

I have not given up on my pi and to satisfy my tinkering itch, I thought to myself: "Why not build a NAS?". And so I did. What follows are steps which I borrowed by sifting through information on the internet (as I am not the first one to do this). This link shows how the author had done it for 3 x 3TB SATA HDDs.

sudo apt-get update
sudo apt-get install mdadm

3 disks is the minimum required count for a RAID5. I'm not sure if having different sizes will work but fortunately, all my disks are 2TBs.

To identify the disks, one can do

cat /proc/partitions

or

lsblk -o NAME,SIZE,FSTYPE,TYPE,MOUNTPOINT

My 3 disks were identified as sda1, sdb1, sdc2. Preparing them for RAID use requires some partitioning. Here's the sequence of commands:

sudo parted
select /dev/sda
mklabel gpt
mkpart primary ext4 1049KB 2TB
select /dev/sdb
mklabel gpt
mkpart primary ext4 1049KB 2TB
select /dev/sdc
mklabel gpt
mkpart primary ext4 1049KB 2TB
quit

After which, the RAID5 can now be created (note the double dashes):

sudo mdadm --create --verbose --force --assume-clean /dev/md0 --level=5 --raid-devices=3 /dev/sda1 /dev/sdb1 /dev/sdc1

To confirm that they are running (note that this command is also useful to know whether the RAID is active after a reboot):

cat /proc/mdstat

Create the ext4 filesystem with (it takes a while to complete as this formats the disks):

sudo mkfs.ext4 -F /dev/md0

Let's create a directory which will be used later as mountpoint:

sudo mkdir -p /mnt/raid5

And mount with:

sudo mount /dev/md0 /mnt/raid5

To check if everything is ok, issue the the following (note that if lost+found is missing, then there's something wrong)

ls -al /mnt/raid5

To check capacity:

df -h -x devtmpfs -x tmpfs

Save the configuration so it starts up at boot time automatically:

sudo mdadm --detail --scan | sudo tee -a /etc/mdadm/mdadm.conf

Raspberry pi uses ramdisk when booting up so we want to include the RAID:

sudo update-initramfs -u

Add the RAID to the filesystem table so it will be mounted automatically when booting up:

echo '/dev/md0 /mnt/raid5 ext4 defaults,nobootwait,nofail 0 0' | sudo tee -a /etc/fstab

Cross your fingers and issue:

sudo reboot

Log back to your pi and again check if lost+found is present:

ls /mnt/raid5

The best thing about experimentation is learning. What do you do when things go out of hand? How do you fix stuff?

(1) Check the state of your RAID:

cat /proc/mdstat

(2) To stop your RAID:

sudo mdadm --stop /dev/md0

(3.1) If your raid doesn't turn up one day first check the result of (take note most specially the /dev/md***):

sudo mdadm --examine --scan 

(3.2) Append the result to the config:

sudo mdadm --examine --scan | sudo tee -a /etc/mdadm/mdadm.conf

(3.3) Edit the entries in your /etc/fstab with the result of (3.1)
(3.4) Reassemble 

sudo mdadm --assemble --scan --force -v /dev/md** /dev/sda1 /dev/sdb1 /dev/sdc1

(4) Identify the disks you have:

cat /proc/partitions





QED












Wednesday, March 16, 2016

Nifty Math Equations

It's a bit unfortunate I can't get latex2html working on my set-up so the equations here will be a bit unattractive.

We know the identity ln (e) = 1. However, have you ever wondered how e is defined?

(1) as x approaches 0, e = lim (1 + x) ^ (1/x)
(2) as x approaches infinity, e = lim (1 + 1/x)^x

Using these 2 basic definitions, we should be able to prove that d/dx (ln x) = 1/x.
We proceed as follows:
d/dx (ln x) = lim [ ln (x+d) - ln (x) ] / d : as d approaches zero
= lim [ ln { (x+d) / x } / d ] : as d approaches zero
= lim [ 1/d * ln { 1 + (d/x) } ] : as d approaches zero
= lim ln {1 + (d/x) } ^ (1/d) : as d approaches zero
Setting u = d/x, we have:
lim ln {1 + (d/x) } ^ (1/d) : as d approaches zero = lim ln (1 + u) ^ (1/u * 1/x) : as u approaches zero
= 1/x ln (1 + u) ^ (1/u)
= 1/x ln (e)
= 1/x
QED

We can now prove further d/dx (e^x) = e^x. Let y = e^x. Taking ln of both sides of the equation, we get
ln (y) = ln (e^x) 
ln (y) = x ln (e) 
ln (y) = x
By implicit differentiation, we get
y'/y = 1
y' = y
Substituting y with its original value, we get
y' = e^x
QED

We can also prove d/dx (a^x) = (a^x) ln (a). Let y = a^x. Taking ln of both sides of the equation, we get
ln (y) = ln (a^x) 
ln (y) = x ln (a) 
By implicit differentiation, we get
y'/y = ln (a)
y' = y ln (a)
Substituting y with its original value, we get
y' = (a^x) ln (a)
QED






Thursday, July 23, 2015

My Second Attempt at Raspberry Pi

Not giving up on my two 16GB Transcend microSDs, I tried writing ubuntu and openelec images - still no joy. Then I tried installing berryboot which got installed properly. Yey!

I chose Raspbian from berryboot and it downloaded fine (after 2 hours of wait time). It got to the point where raspi-config was up and running. Then it rebooted.

A lot of errors appeared on the screen! I waited till i showed the login prompt. I tried logging in but I kept getting errors and it would even ask for the password. That's the closest I got with Transcend.

Then I bought a Samsung EVO with model code : MB-MP08DA/JP.

Formatted it using SD Formatter 4.0 (mentioned in previous blog). Copied the contents of NOOBS and with fingers crossed, attempted to install Raspbian.

To my surprise, it worked! I'm keeping this config. 

TO ALL MY FELLOW ADVENTURERS: THERE IS SUCH A THING THAT GOOD AND BAD COMPATIBILITIES OF SD CARDS FOR RASPBERRY PI 2 MODEL B!

Monday, July 20, 2015

My First Attempt with Raspberry Pi

I decided to ride on the Raspberry Pi bandwagon. I ordered two "Raspberry Pi 2 Model B" from Amazon with clear case enclosure as I didn't want to waste time scavenging for covers, and two Transcend micro SD 16 GB class 10.

What I didn't know is that it needed a power source (which is sold separately of course)! After looking around for spare smart phone chargers I had a few years back and found out that they've already been disposed, I went to a local electronic shop and bought two micro USB cable adapters. I'm planning to re-use the iPhone USB charger that I have to initially power my first ever Raspberry Pi.

My main computer is a late 2009 model MacBook Pro running the latest version of Yosemite.

When I've finally managed to get all the necessary parts and scouring the web regarding installation of NOOBS here's where I got to:

  1. I downloaded and installed SD Formatter 4.0 for Mac
  2. I first downloaded NOOBS
  3. I formatted both micro SDs using the softwared installed in 1
When I finally plugged the cables, and the SD card to my Raspberry Pi hoping that it will be an easy install, I was disappointed when I got below error:


Error creating file system
mkfs.fat:warning lowercase lables might not work properly with DOS or windows
mkfs.fat: failed whilst writing FAT
mkfs.fat 3.0.26(2014-03-07) 


Googling it didn't yield useful results! Some say, micro SD is busted, etc. which i refuse to believe.

What I decided next is to install the Raspbian image onto the micro SD. So I downloaded the image via bittorrent and after 2 hours of waiting, got to the point where I believe I should follow the command line instructions.

  1. Open Terminal app
  2. df -h
  3. Insert micro SD to card reader
  4. df -h (the device was recognized as /dev/disk3s1)
  5. sudo diskutil unmount /dev/disk3s1
  6. sudo dd bs=1m if="/path/to/your/2015-05-05-raspbian-wheezy.img" of=/dev/rdisk3 (I followed the alternative route)
  7. sudo diskutil eject /dev/rdisk3
Here's some output:


3125+0 records in
3125+0 records out
3276800000 bytes transferred in 257.798126 secs (12710721 bytes/sec)

I have now plugged the power cable and tried booting while writing this down, and it's taking an aweful lot of time.

I'm now getting a kernel panic error - sigh.