2
\$\begingroup\$

EDIT

The random number generator in this code is a blackbox for a similar algorithm that isn't publishable for privacy concern. The algorithm works in similar way, in that it takes in a seed value and generates number.

Simplifying the question

The corrupted references are from a text file, there are thousands of those reference numbers. I'm tasked to create a program that will take in one reference from the text file, then brute force the algorithm through to find the seed that generated the number.

The generated numbers are in reversed, so just brute forcing will not get you the right number, you will have to reverse the brute number and check if it matches with the reference number, if yes then print the seed number and get the next reference number.

Since the seeds value are from 100 million to 999 million, we have to brute force through those to find the right seed value. it takes 4 minute to brute force a single reference number and I have hundreds of thousands of the numbers to go through. How can I make it super fast?

I tried putting the references in arraylist on first load since it's just 900 million list of reference and then use indexOF, but it gives me outofmemory error.

Product Version: Apache NetBeans IDE 9.0 (Build incubator-netbeans-release-334-on-20180708)

Java: 11.0.1; Java HotSpot(TM) 64-Bit Server VM 11.0.1+13-LTS

Runtime: Java(TM) SE Runtime Environment 11.0.1+13-LTS

System: Mac OS X version 10.13.6 running on x86_64; UTF-8; en_GB (nb)

import java.io.FileNotFoundException;
import java.io.UnsupportedEncodingException;
import java.util.Random;
import java.util.ArrayList;
/**
 *
 * @author HJoe
 */
public class idResolver {

    /**
     * @param args
     * @throws java.io.FileNotFoundException
     * @throws java.io.UnsupportedEncodingException
     */
    public static void main(String[] args) throws FileNotFoundException, UnsupportedEncodingException {
    ArrayList corruptedReferences = new ArrayList();
    Stream<String> lines = Files.lines(Paths.get("/Users/kingamada/Documents/Corrupted References.txt"));
    lines.forEach(l -> {
        corruptedReferences.add(l);
    });
        StringBuilder sb = new StringBuilder();
        int max = 1000000000;
        int min = 100000000;
        long nano_startTime = System.nanoTime();
        long millis_startTime = System.currentTimeMillis();
        for (int i = 0; i < corruptedReferences.size(); i++) {
            long corruptIDNumbers =corruptedReferences.get(i);
            for (int n = min; n < max; n++) {
                Random rand = new Random(n);
                long findID = rand.nextLong();
                sb.append(findID);
                //String reverseID = reverse(String.valueOf(findID));
                findID = Long.valueOf(sb.reverse().toString().substring(0, 9));
                if (findID == corruptIDNumbers) {
                    //System.out.println("Found the ID:  "+n);
                    break;
                }
                sb.setLength(0);

            }
            long nano_endTime = System.nanoTime();
            long millis_endTime = System.currentTimeMillis();

            System.out.println("Time taken in nano seconds: "
                + (nano_endTime - nano_startTime));
            System.out.println("Time taken in milli seconds: "
                + (millis_endTime - millis_startTime));

        }
    }

    public static String reverse(String input) {
        char[] in = input.toCharArray();
        int begin = 0;
        int end = in.length - 1;
        char temp;
        while (end > begin) {
            temp = in[begin];
            in[begin] = in[end];
            in[end] = temp;
            end--;
            begin++;
        }
        return new String(in);
    }

    public static long reverseID(Long idNumber) {
        String s = String.valueOf(idNumber);
        StringBuilder sb = new StringBuilder();
        for (int n = 0; n < s.length(); n++) {
            sb.append(s.charAt((s.length() - n) - 1));
        }
        s = sb.toString();
        long reversedNumber = Long.valueOf(s);
        return reversedNumber;

    }
}
\$\endgroup\$
  • \$\begingroup\$ The Java major version is somewhat relevant here, but the other versions basically aren't. \$\endgroup\$ – Reinderien Oct 12 at 21:10
  • \$\begingroup\$ I have.. a lot of questions, and they'll balloon the comments section. Let's please discuss in chat.stackexchange.com/rooms/99828/… \$\endgroup\$ – Reinderien Oct 12 at 22:47
  • \$\begingroup\$ Given what I've learned in chat, it's important that you edit this question to include: the estimated number of corrupted IDs (certainly not 11); the fact that random is actually a black-box function that isn't publishable over privacy concerns; and some parsing code showing how you'll be getting the IDs from a text file. \$\endgroup\$ – Reinderien Oct 12 at 23:15
  • \$\begingroup\$ I realize that you can't show us the RNG, but can you look at it? Are you able to at least narrow down the initial seeds by calculating the first one or two random numbers exactly? \$\endgroup\$ – markspace Oct 13 at 0:15
  • 1
    \$\begingroup\$ I'm not sure. Basically what I'm saying is that if you know what the first value you want out of an RNG is, you should be able to tell pretty quickly which seed will give you that number. It should cut down on the search, maybe by a factor of 200 or so. Second idea just occurred to me now: I think a "rainbow table" is a table of all possible values for a hash, so you can do a reverse look-up to crack a password hash. Can you calculate all 100 million seeds once and then just look them up? Again the idea is to reduce the number of possible values you have to search. \$\endgroup\$ – markspace Oct 13 at 0:35
4
\$\begingroup\$

The first and easiest option is to turn your loops inside-out. In your inner loop, you reverse the corrupt numbers. That shouldn't even be done in your main loop - just do it once, making a reversedIDs after initializing your corruptIDNumbers.

Your for (int i = 0; i < 1; i++) doesn't make a lot of sense, and is probably just you manually truncating the program due to the runtime. But it should go away completely. Instead, make a HashSet containing your reversedIDs, and do not iterate over this set. On every randomly generated number, test to see if the generated number is a member of the set.

Another important thing to do, since your brute-force approach is CPU-bound and highly parallelizable, is to multi-thread. Here is a suggested multi-threaded brute-force approach that completes for me in 5 seconds.

You'll of course want to change the number of workers to suit your CPU.

import java.io.FileInputStream;
import java.io.IOException;
import java.util.HashSet;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;


public class IDResolver implements AutoCloseable {
    // This class is intended to be instantiated. main() is a thin entry point.

    // The set of all IDs as read from the file. Modern RAM capacity will easily
    // fit hundreds of thousands of IDs at once.
    private final Set<Long> ids = new HashSet<>();

    // The number of threads to run. Do not increase this beyond the hyperthread
    // capacity of your CPU or you will see steeply diminishing returns.
    private final int nworkers = 8;

    // The array of all Thread worker objects.
    private final Worker[] workers = new Worker[nworkers];

    // The upper and lower bound of the seed search space.
    private final long seedMin = 100_000_000,
                       seedMax = 1_000_000_000;

    // The constructor; accepts the name of the file containing IDs, one per
    // line.
    public IDResolver(String filename) throws IOException {
        populate(filename);

        // The start of each worker's seed search space; computed incrementally.
        long start = seedMin;

        System.out.println("Workers:");

        // Loop to create each worker and print its summary.
        for (int w = 0; w < nworkers; w++) {
            long end;
            if (w == nworkers-1)
                end = seedMax;
             else
                end = (seedMax - seedMin)*(w + 1)/nworkers + seedMin;

            workers[w] = new Worker(w, w==nworkers-1, start, end);
            System.out.println(workers[w]);
            start = end;
        }
        System.out.println();
    }

    // Populate the ID set from the ID file. Each ID is string-reversed before
    // being added to the set.
    private void populate(String filename) throws IOException {
        try (var stream = new FileInputStream(filename);
             var scanner = new Scanner(stream)) {
             var sb = new StringBuilder();

             while (true) {
                String line;
                try {
                    line = scanner.nextLine();
                } catch (NoSuchElementException e) {
                    break;
                }
                sb.append(line);
                long id = Long.valueOf(sb.reverse().toString());
                ids.add(id);
                sb.setLength(0);
             }
        }
    }

    // Entry point for the program. This program accepts one argument, the ID
    // file name.
    public static void main(String[] args) throws Exception {
        try (var resolver = new IDResolver(args[0])) {
            resolver.resolve();
            resolver.join();
        }
    }

    // Resolve all IDs by starting the worker threads.
    public void resolve() {
        for (Worker w: workers)
            w.start();
    }

    // Wait until all of the worker threads are done.
    public void join() throws InterruptedException {
        for (Worker w: workers)
            w.join();
    }

    // When this class is used as an AutoCloseable within a try-with-resources,
    // and close() is called, cancel the worker threads.
    public void close() throws InterruptedException {
        for (Worker w: workers) {
            w.cancel();
            w.join();
        }
    }

    // This is the "black box" function that needs to be replaced with your own.
    // It accepts a seed and returns an ID.
    private static long transform(long seed) {
        // todo: replace me
        var rand = new Random(seed);
        return rand.nextLong();
    }

    // The worker thread class. This supports all of the methods of Thread,
    // notably start().
    private class Worker extends Thread {
        // This is used to control the frequency of progress updates. Change the
        // 24, increasing it for slower updates.
        final long updateMask = (1L << 24) - 1;

        final int worker; // The worker's ID
        final long start; // The start of this worker's seed range
        long end; // The (exclusive) end of this worker's seed range
        final boolean last; // Whether this is the last worker

        public Worker(int worker, boolean last, long start, long end) {
            this.worker = worker;
            this.last = last;
            this.start = start;
            this.end = end;
        }

        // Used to show a summary of this worker
        @Override
        public String toString() {
            return String.format("ID=%d range %10d - %10d", worker, start, end);
        }

        // Show progress - only used on the last worker
        private void tick(long seed) {
            if (last) {
                System.out.print(String.format(
                    "seed=%,d/%,d %.2f%%\r", seed, end,
                    (seed - start)*100. / (end - start)
                ));
            }
        }

        // The worker thread routine.
        public void run() {
            // Loop through all seeds for this worker.
            for (long seed = start; seed < end; seed++) {
                // The candidate ID, as transformed from the current seed.
                long id = transform(seed);
                // Does this candidate ID exist in the set of all known IDs from
                // the file?
                if (ids.contains(id))
                    // If so, print the seed and the ID that it produced.
                    System.out.println(String.format(
                        "seed=%d id=%d", seed, id));
                // Show progress.
                if ((seed&updateMask) == 0)
                    tick(seed);
            }

            tick(end);
            if (last)
                System.out.println();
        }

        // Cancel this worker by setting its seed range end to zero.
        public void cancel() {
            end = 0;
        }
    }
}

Invocation and output:

$ javac IDResolver.java && time java IDResolver corrupted.txt 
Workers:
ID=0 range  100000000 -  212500000
ID=1 range  212500000 -  325000000
ID=2 range  325000000 -  437500000
ID=3 range  437500000 -  550000000
ID=4 range  550000000 -  662500000
ID=5 range  662500000 -  775000000
ID=6 range  775000000 -  887500000
ID=7 range  887500000 - 1000000000

seed=1,000,000,000/1,000,000,000 100.00%

real    0m4.784s
user    0m36.266s
sys 0m0.308s
\$\endgroup\$
  • \$\begingroup\$ Thanks for your feedback and recommendations, I think the best way is to have ti make the reverse IDs as you have mentioned, but can a HashSet hold over 900million references? \$\endgroup\$ – Hither Joe Oct 12 at 22:24
  • \$\begingroup\$ Currently you only show 11 corrupt IDs. Is it that list that's expected to increase to 900 million? \$\endgroup\$ – Reinderien Oct 12 at 22:33
  • \$\begingroup\$ Yes, it's intended to reach hundreds of thousands, but the indexes(nth value used s seed) is expected to reach up to 900 million. \$\endgroup\$ – Hither Joe Oct 12 at 22:42
  • \$\begingroup\$ @HitherJoe Please refer to edit. As long as your "black box" isn't massively more complex than random, this will complete quickly. \$\endgroup\$ – Reinderien Oct 13 at 14:25
  • \$\begingroup\$ Thanks for the code, it has increase the performance significantly, but it's still slow. I'm new to multi threading, I assume by increasing number of workers, the speed should increase right? I increased workers to 1000 but the speed still remain almost the same. Using the BlackBox algorithm it took 7minutes to process 10 IDs, my former code takes 4minute per ID. Even using the random function it still takes time. It would be great if you will comment the the use of functions/methods in your code, it will help me understand it well to edit it to fit my need. \$\endgroup\$ – Hither Joe Oct 14 at 6:30
1
\$\begingroup\$

A couple of things that might help:

To reverse a number, it is more efficient to use math instead of converting the number to a string first. Something like this should work:

public static long reverseID(Long idNumber){
    Long retVal = 0l;
    while(idNumber > 0){
        retVal = (retVal * 10) + (idNumber % 10);
        input /= 10;
    }
    return retVal;
}

Also you can simplify, and possibly make more efficient, the reverse method by using the StringBuilder.reverse() method:

public static String revString(String input){
    return new StringBuilder(input).reverse().toString();
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for your suggestion, but if you look through the code, I used the StringBuilder.reverse method already. \$\endgroup\$ – Hither Joe Oct 13 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.