Skip to content

A mostly POSIX-compliant utility that scans a given interval for vampire numbers.

License

Notifications You must be signed in to change notification settings

plerros/helsing

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 

Repository files navigation

Helsing

Helsing is a command-line program that scans intervals for vampire numbers.

helsing_gif

The default algorithm has a time complexity of $O(n)$ and a space complexity of $O(\sqrt{n})$.

In helsing/configuration.h you can toggle the algorithms and tune them, adjust verbosity, change the numeral base system, set a minimum fang pairs filter, and enable resume from checkpoint. Be sure to read the documentation.

Windows Preparation

Helsing uses posix threads, and since Windows isn't posix compatible, you'll need to install WSL.

Note that the guide above will install WSL with Ubuntu, so you'll have to follow the Ubuntu instructions.

MacOS Preparation

On MacOS you'll have to install homebrew.

Installation

  1. Install dependencies

    Platform Install Install optional
    MacOS brew install git gcc gmake findutils brew install openssl (broken)
    Debian/Ubuntu sudo apt install git gcc make findutils sudo apt install libssl-dev
    Fedora/RHEL sudo dnf install git gcc make findutils sudo dnf install openssl-devel
    FreeBSD: pkg install git gcc gmake findutils pkg install openssl-devel
    HaikuOS pkgman install git gcc make findutils (pre-installed)
    Openindiana pkg install git gcc gmake findutils pkg install library/security/openssl-11
    You can also use clang instead of gcc
  2. Download

    git clone https://github.com/plerros/helsing.git
    cd helsing/helsing
    
  3. Compile

    Platform Compile
    MacOS gmake
    Debian/Ubuntu make
    Fedora/RHEL make
    FreeBSD: gmake
    HaikuOS make
    Openindiana gmake

Run

./helsing -l min -u max

Examples:

$ ./helsing -l 1260 -u 1260
Checking interval: [1260, 1260]
Found: 1 vampire number(s).

$ ./helsing -l 0 -u 1172560176
Adjusted min from 0 to 10
Checking interval: [10, 99]
Checking interval: [1000, 9999]
Checking interval: [100000, 999999]
Checking interval: [10000000, 99999999]
Checking interval: [1000000000, 1172560176]
Found: 10000 vampire number(s).

$ ./helsing -l 18446744073709551615 -u 18446744073709551615
Checking interval: [18446744073709551615, 18446744073709551615]
Found: 0 vampire number(s).

Run for all n-digit numbers

./helsing -n number_of_digits

Examples:

$ ./helsing -n 2
Checking interval: [10, 99]
Found: 0 vampire number(s).

$ ./helsing -n 4
Checking interval: [1000, 9999]
Found: 7 vampire number(s).

$ ./helsing -n 12
Checking interval: [100000000000, 999999999999]
Found: 4390670 vampire number(s).

$ ./helsing -n 14
Checking interval: [10000000000000, 99999999999999]
Found: 208423682 vampire number(s).

$ ./helsing -n 16
Checking interval: [1000000000000000, 9999999999999999]
Found: 11039126154 vampire number(s).

Set the number of threads

./helsing -t threads

Examples:

$ time ./helsing -n 12 -t 1
Checking interval: [100000000000, 999999999999]
Found: 4390670 vampire number(s).

real	0m36.781s
user	0m36.678s
sys	0m0.025s

$ time ./helsing -n 12 -t 2
Checking interval: [100000000000, 999999999999]
Found: 4390670 vampire number(s).

real	0m18.592s
user	0m36.581s
sys	0m0.037s

$ time ./helsing -n 12 -t 4
Checking interval: [100000000000, 999999999999]
Found: 4390670 vampire number(s).

real	0m9.402s
user	0m37.361s
sys	0m0.041s

time ./helsing -n 12 -t 8
Checking interval: [100000000000, 999999999999]
Found: 4390670 vampire number(s).

real	0m4.913s
user	0m38.510s
sys	0m0.044s

time ./helsing -n 12 -t 12
Checking interval: [100000000000, 999999999999]
Found: 4390670 vampire number(s).

real	0m3.344s
user	0m39.233s
sys	0m0.030s

Display progress

./helsing --progress

Example:

$ ./helsing -n 12 --progress
Checking interval: [100000000000, 999999999999]
100000000000, 199999999999  1/9
200000000000, 299999999999  2/9
300000000000, 399999999999  3/9
400000000000, 499999999999  4/9
500000000000, 599999999999  5/9
600000000000, 699999999999  6/9
700000000000, 799999999999  7/9
800000000000, 899999999999  8/9
900000000000, 999998000001  9/9
Found: 4390670 vampire number(s).

Dry run

./helsing --dry-run

Example:

$ ./helsing -l 0 -u 18446744073709551615 --dry-run
Adjusted min from 0 to 10
Checking interval: [10, 99]
Checking interval: [1000, 9999]
Checking interval: [100000, 999999]
Checking interval: [10000000, 99999999]
Checking interval: [1000000000, 9999999999]
Checking interval: [100000000000, 999999999999]
Checking interval: [10000000000000, 99999999999999]
Checking interval: [1000000000000000, 9999999999999999]
Checking interval: [100000000000000000, 999999999999999999]
Checking interval: [10000000000000000000, 18446744073709551615]
Found: 0 vampire number(s).

Display build configuration

./helsing --buildconf

Example:

$ ./helsing --buildconf
  configuration:
    VERBOSE_LEVEL=2
    MIN_FANG_PAIRS=1
    MAX_FANG_PAIRS=1
    MEASURE_RUNTIME=false
    ALG_NORMAL=false
    ALG_CACHE=true
    COMPARISON_BITS=64
    PARTITION_METHOD=0
    MULTIPLICAND_PARTITIONS=2
    PRODUCT_PARTITIONS=3
    BASE=10
    MAX_TASK_SIZE=99999999999
    USE_CHECKPOINT=false
    LINK_SIZE=100
    SAFETY_CHECKS=false

Recover from checkpoint (if enabled in configuration)

./helsing