Git Product home page Git Product logo

helsing's Introduction

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
    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

helsing's People

Contributors

jaskij avatar plerros avatar

Stargazers

avatar avatar avatar

Watchers

avatar

Forkers

jaskij

helsing's Issues

PDEP causes false result

With a numeral base system of 12, the expected behavior is:

$ ./helsing -l 8879963803050 -u 8879963803050
Found: 1 vampire number(s).

but if we enable pdep

$ ./helsing -l 8879963803050 -u 8879963803050
Found: 0 vampire number(s).

lcrypto not linked

Compilation on Ubuntu 21.04 fails with:
undefined reference to 'OPENSSL_init_crypto'

cache 32 regression

Setting cache to 32 can result in 8~13 % performance regression on some 64-bit systems.

Defining NDEBUG breaks the build

While working on #37 any sort of release build was segfaulting. After some investigation I found out that the reason for this is that CMake defaults to defining NDEBUG in release builds. Looking at

helsing/helsing/src/main.c

Line 65 in 1f27c7d

assert(pthread_create(&threads[thread], NULL, thread_function, (void *)(thhandle->targs[thread])) == 0);
it becomes obvious that disabling asserts would not create the threads, and the later pthread_join segfaults.

A possible fix, which I confirmed to work, is:

diff --git a/helsing/src/main.c b/helsing/src/main.c
index f0028c6..4ee5bba 100644
--- a/helsing/src/main.c
+++ b/helsing/src/main.c
@@ -61,8 +61,10 @@ int main(int argc, char *argv[])
 			continue;
 
 		fprintf(stderr, "Checking interval: [%llu, %llu]\n", lmin, lmax);
-		for (thread_t thread = 0; thread < options.threads; thread++)
-			assert(pthread_create(&threads[thread], NULL, thread_function, (void *)(thhandle->targs[thread])) == 0);
+		for (thread_t thread = 0; thread < options.threads; thread++) {
+			int pthread_create_return = pthread_create(&threads[thread], NULL, thread_function, (void*) (thhandle->targs[thread]));
+			assert(pthread_create_return == 0);
+		}
 		for (thread_t thread = 0; thread < options.threads; thread++)
 			pthread_join(threads[thread], 0);
 	}

Skips 20 digit numbers

Compile & Run:

$ make
...
$ ./helsing -l 10000000000000000000 -u 10000000000000000000

Expected behavior:

Checking interval: [10000000000000000000, 10000000000000000000]
Found: 0 vampire number(s).

Actual behavior:

Found: 0 vampire number(s).

thinks that 544 is vampire when CACHE = false and BASE = 2

Set in configuration.h:

  1. VERBOSE_LEVEL 1
  2. CACHE false
  3. BASE 2

Compile & Run:

make
./helsing -l 544 -u 544

Result:

Checking interval: [544, 544]
544 = 32 x 17
Found: 1 valid fang pairs.

This is not a vampire number, because 544 is 10 digit (in base 2) and the fang pairs should be 10/2 = 5 digit, but 32 is 6 digit

continues from checkpoint even after completion

Set in configuration.h:
CHECKPOINT true

Compile & Run:

$ make
...
$ ./helsing -t 1 -n 4
Checking interval: [1000, 9999]
Found: 7 vampire number(s).
$ cat a.checkpoint 
1000 9999
2466 6
3933 6
5400 6
6867 6
8334 7
9801 7

(It stops at 9801, because there are no vampire numbers in the range [9802, 9999])
The program completed, and we got our results.
If we were to resume from checkpoint, the program shouldn't calculate anything and the checkpoint file shouldn't change:

$ ./helsing -t 1
Found: 7 vampire number(s).
$ cat a.checkpoint 
1000 9999
2466 6
3933 6
5400 6
6867 6
8334 7
9801 7

However:

$ ./helsing -t 1
Checking interval: [9802, 9999]
Found: 7 vampire number(s).
$ cat a.checkpoint 
1000 9999
2466 6
3933 6
5400 6
6867 6
8334 7
9801 7
9834 7
9867 7
9900 7
9933 7
9966 7
9999 7

options uninitialized warning when using flto

When compiling with -flto:

In function ‘taskboard_new’,
    inlined from ‘main’ at src/main.c:44:2:
src/task/taskboard.c:30:22: warning: ‘options.min’ may be used uninitialized [-Wmaybe-uninitialized]
   30 |         new->options = options;
      |                      ^
src/main.c: In function ‘main’:
src/main.c:33:26: note: ‘options.min’ was declared here
   33 |         struct options_t options;
      |                          ^
In function ‘taskboard_new’,
    inlined from ‘main’ at src/main.c:44:2:
src/task/taskboard.c:30:22: warning: ‘options.max’ may be used uninitialized [-Wmaybe-uninitialized]
   30 |         new->options = options;
      |                      ^
src/main.c: In function ‘main’:
src/main.c:33:26: note: ‘options.max’ was declared here
   33 |         struct options_t options;
      |                          ^

make CC=clang: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x 

$ make CC=clang
mkdir -p build/./src/array/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/array/array.c -o build/./src/array/array.c.o
src/array/array.c:54:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   54 |         OPTIONAL_ASSERT(ptr != NULL);
      |                        ^
src/array/array.c:55:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   55 |         OPTIONAL_ASSERT(*ptr == NULL);
      |                        ^
src/array/array.c:56:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   56 |         OPTIONAL_ASSERT(count_ptr != NULL);
      |                        ^
3 warnings generated.
mkdir -p build/./src/checkpoint/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/checkpoint/checkpoint.c -o build/./src/checkpoint/checkpoint.c.o
mkdir -p build/./src/hash/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/hash/hash.c -o build/./src/hash/hash.c.o
mkdir -p build/./src/helper/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/helper/helper.c -o build/./src/helper/helper.c.o
src/helper/helper.c:40:50: warning: too many arguments in call to 'no_args'
   40 |         OPTIONAL_ASSERT(exponent <= length(VAMP_MAX) - 1);
      |         ~~~~~~~~~~~~~~~                                 ^
src/helper/helper.c:40:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   40 |         OPTIONAL_ASSERT(exponent <= length(VAMP_MAX) - 1);
      |                        ^
2 warnings generated.
mkdir -p build/./src/interval/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/interval/interval.c -o build/./src/interval/interval.c.o
mkdir -p build/./src/linked_list/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/linked_list/llnode.c -o build/./src/linked_list/llnode.c.o
src/linked_list/llnode.c:23:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   23 |         OPTIONAL_ASSERT(ptr != NULL);
      |                        ^
src/linked_list/llnode.c:24:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   24 |         OPTIONAL_ASSERT(*ptr == NULL);
      |                        ^
src/linked_list/llnode.c:54:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   54 |         OPTIONAL_ASSERT(ptr != NULL);
      |                        ^
src/linked_list/llnode.c:55:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   55 |         OPTIONAL_ASSERT(value != 0);
      |                        ^
4 warnings generated.
mkdir -p build/./src/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/main.c -o build/./src/main.c.o
mkdir -p build/./src/options/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/options/options.c -o build/./src/options/options.c.o
mkdir -p build/./src/task/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/task/taskboard.c -o build/./src/task/taskboard.c.o
src/task/taskboard.c:23:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   23 |         OPTIONAL_ASSERT(ptr != NULL);
      |                        ^
src/task/taskboard.c:24:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   24 |         OPTIONAL_ASSERT(*ptr == NULL);
      |                        ^
2 warnings generated.
mkdir -p build/./src/task/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/task/task.c -o build/./src/task/task.c.o
src/task/task.c:18:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   18 |         OPTIONAL_ASSERT(ptr != NULL);
      |                        ^
src/task/task.c:19:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   19 |         OPTIONAL_ASSERT(*ptr == NULL);
      |                        ^
src/task/task.c:44:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   44 |         OPTIONAL_ASSERT(ptr != NULL);
      |                        ^
src/task/task.c:45:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   45 |         OPTIONAL_ASSERT(vamp_args != NULL);
      |                        ^
4 warnings generated.
mkdir -p build/./src/thread/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/thread/targs.c -o build/./src/thread/targs.c.o
src/thread/targs.c:28:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   28 |         OPTIONAL_ASSERT(ptr != NULL);
      |                        ^
src/thread/targs.c:29:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   29 |         OPTIONAL_ASSERT(*ptr == NULL);
      |                        ^
2 warnings generated.
mkdir -p build/./src/thread/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/thread/targs_handle.c -o build/./src/thread/targs_handle.c.o
src/thread/targs_handle.c:20:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   20 |         OPTIONAL_ASSERT(ptr != NULL);
      |                        ^
src/thread/targs_handle.c:21:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   21 |         OPTIONAL_ASSERT(*ptr == NULL);
      |                        ^
2 warnings generated.
mkdir -p build/./src/vampire/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/vampire/cache.c -o build/./src/vampire/cache.c.o
src/vampire/cache.c:31:18: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   31 |                 OPTIONAL_ASSERT(tmp[i] < DIGBASE(ACTIVE_BITS));
      |                                ^
src/vampire/cache.c:40:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   40 |         OPTIONAL_ASSERT(ptr != NULL);
      |                        ^
src/vampire/cache.c:41:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
   41 |         OPTIONAL_ASSERT(*ptr == NULL);
      |                        ^
3 warnings generated.
mkdir -p build/./src/vampire/
clang -I. -I./src -I./src/array -I./src/checkpoint -I./src/hash -I./src/helper -I./src/interval -I./src/linked_list -I./src/options -I./src/task -I./src/thread -I./src/vampire -MMD -MP -Wall -Wextra  -O2 -c src/vampire/vargs.c -o build/./src/vampire/vargs.c.o
src/vampire/vargs.c:103:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
  103 |         OPTIONAL_ASSERT(ptr != NULL);
      |                        ^
src/vampire/vargs.c:104:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
  104 |         OPTIONAL_ASSERT(*ptr == NULL);
      |                        ^
src/vampire/vargs.c:231:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
  231 |         OPTIONAL_ASSERT(ptr != NULL);
      |                        ^
src/vampire/vargs.c:334:17: warning: passing arguments to 'no_args' without a prototype is deprecated in all versions of C and is not supported in C2x [-Wdeprecated-non-prototype]
  334 |         OPTIONAL_ASSERT(ptr->product[3 - 1].iterator == 0);
      |                        ^
4 warnings generated.
clang -Wall -Wextra  -O2  build/./src/array/array.c.o build/./src/checkpoint/checkpoint.c.o build/./src/hash/hash.c.o build/./src/helper/helper.c.o build/./src/interval/interval.c.o build/./src/linked_list/llnode.c.o build/./src/main.c.o build/./src/options/options.c.o build/./src/task/taskboard.c.o build/./src/task/task.c.o build/./src/thread/targs.c.o build/./src/thread/targs_handle.c.o build/./src/vampire/cache.c.o build/./src/vampire/vargs.c.o -o helsing  -lpthread -lm

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.