Skip to content

Instantly share code, notes, and snippets.

@mjtb49
Created September 27, 2020 20:21
Show Gist options
  • Save mjtb49/c62dec80efb6af1adfae9a146b3b09c1 to your computer and use it in GitHub Desktop.
Save mjtb49/c62dec80efb6af1adfae9a146b3b09c1 to your computer and use it in GitHub Desktop.
A class providing a fast algorithm for converting a 48 bit structure seed to a nextLong with the same lower 48 bits.
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class NextLongEquivalentFinder {
//{0, 107048004364969} offsets
//{{-33441*2/(32768*2), 46603/65536}, {17549*2/(32768*2), 39761/65536}}/65536 will be our inverse matrix
/**
* Adds seeds which give nextLongs congruent to your structure seed to a list.
* Has a precondition that structureSeed is 48 bits (its upper 16 bits as a long are 0)
* @param structureSeed the 48 bit version of the seed
* @param seedList a list to add the seeds to
*/
public static void addSeedsToList(long structureSeed, List<Long> seedList) {
long lowerBits = structureSeed & 0xffff_ffffL;
long upperBits = structureSeed >>> 32;
//Did the lower bits affect the upper bits
if ((lowerBits & 0x8000_0000L) != 0)
upperBits += 1; //restoring the initial value of the upper bits
BigDecimal lowMin = BigDecimal.valueOf(lowerBits << 16);
BigDecimal lowMax = BigDecimal.valueOf(((lowerBits + 1) << 16) - 1);
//the next two lines seem to only barely require the BigDecimals, so they can probably be avoided if you're careful
BigDecimal upperMin = BigDecimal.valueOf((upperBits << 16) - 107048004364969L);
//hardcoded matrix multiplication again
BigDecimal min1 = lowMax.multiply(BigDecimal.valueOf(-33441*2)).add(upperMin.multiply(BigDecimal.valueOf(17549*2))).divide(BigDecimal.valueOf(1L << 32), RoundingMode.CEILING);
BigDecimal min2 = lowMin.multiply(BigDecimal.valueOf(46603)).add(upperMin.multiply(BigDecimal.valueOf(39761))).divide(BigDecimal.valueOf(1L << 32), RoundingMode.CEILING);
long m1lv = min1.longValue();
long m2lv = min2.longValue();
//with a lot more effort you can make these loops check 2 things and not 4 but I'm not sure it would even be much faster
for (int i = 0; i <=1; i++) for (int j = 0; j <=1; j++) {
long seed = (-39761 * (m1lv + i) + 35098 * (m2lv + j));
if ((46603 * (m1lv + i) + 66882 * (m2lv + j)) + 107048004364969L >>> 16 == upperBits) {
if (seed >>> 16 == lowerBits)
seedList.add((254681119335897L * seed + 120305458776662L) & 0xffff_ffff_ffffL);
}
}
}
/**
* Returns of list of seeds which give nextLongs congruent to your structure seed.
* Has a precondition that structureSeed is 48 bits (its upper 16 bits as a long are 0)
* @param structureSeed the 48 bit version of the seed
*/
public static ArrayList<Long> getSeeds(long structureSeed) {
ArrayList<Long> seeds = new ArrayList<>(2);
addSeedsToList(structureSeed,seeds);
return seeds;
}
/**
* Adds nextLongs congruent to your structure seed to a list.
* Has a precondition that structureSeed is 48 bits (its upper 16 bits as a long are 0)
* @param structureSeed the 48 bit version of the seed
* @param nextLongs a list to add the nextLongs to
*/
public static void addNextLongEquivalents(long structureSeed, List<Long> nextLongs) {
//this technically does some redundant operations
for (long seed: getSeeds(structureSeed)) {
nextLongs.add(new Random(seed ^ 0x5deece66dL).nextLong());
}
}
/**
* Returns of nextLongs congruent to your structure seed.
* Has a precondition that structureSeed is 48 bits (its upper 16 bits as a long are 0)
* @param structureSeed the 48 bit version of the seed
*/
public static ArrayList<Long> getNextLongEquivalents(long structureSeed) {
ArrayList<Long> nextLongs = new ArrayList<>(2);
addNextLongEquivalents(structureSeed,nextLongs);
return nextLongs;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment