jakobkogler

BigInteger library

Compile the program

$ g++ -std=c++17 main.cpp -Ofast -o biginteger_benchmark

Run it with 1'000'000 digits

jakobkogler

>> g++ -std=c++20 -Ofast a.cpp && ./a.out
N = 30000000: 
    norm:     bool: 157 ms 1857859
    norm:     char: 257 ms 1857859
    norm:     bool is 1.637 times FASTER
    seg:      bool: 177 ms 1857859
    seg:      char: 57 ms 1857859
    seg:      bool is 3.105 times SLOWER
    seg opt:  char: 19 ms 1857859

jakobkogler

>> g++ -std=c++20 -Ofast benchmark_prime_sieve.cpp && ./a.out
N = 30000000: 
    norm: bool: 106 ms
    norm: char: 235 ms
    norm: bool is 2.217 times FASTER
    seg:  bool: 147 ms
    seg:  char: 38 ms
    seg:  bool is 3.868 times SLOWER

N = 60000000: 

jakobkogler

#include <bits/stdc++.h>
using namespace std;

const int mod = 7340033;
const int root = 5;
const int root_1 = 4404020;
const int root_pw = 1 << 20;

long long inverse(long long x, int mod) {
    long long res = 1;

jakobkogler

#include <bits/stdc++.h>
using namespace std;
const int N = 1e8;
bool comp[N];
vector<int> primes;

void normal_sieve() {
    memset(comp, 0, sizeof comp);

    primes.clear();

jakobkogler

#!/usr/bin/env python3

import urllib.request
import json
from datetime import datetime, timedelta
import matplotlib.pyplot as plt
from matplotlib.dates import drange
from collections import defaultdict
import sys

jakobkogler

14 cpp files
6 static libs, + a few header only libs

Linux (cmake + gcc):
recompile everything
17 sec / 21 sec
Only one change: 5.6 seconds

Windows (VS 2015):
Only 2 static libs, the other 4 dynamic

jakobkogler

#!/bin/bash

FILEPATH=$1
FILENAME=$(echo "$FILEPATH" | sed 's/\..*//')
LENGTH=$2

DURATION=$(ffmpeg -i $FILEPATH 2>&1 | grep Duration | sed 's/Duration: \(.*\), start.*/\1/g')
DURATION=$(echo $DURATION | awk -F: '{ print ($1 * 60) + $2 }')
PARTS=$(((DURATION + LENGTH - 1) / LENGTH))

jakobkogler

Diamant-Adhoc

Naive (einfache) Lösung

Hilfsmethode

Zuerst definiere ich eine kleine Hilfsmethode, die es ermöglicht mehrere Zeichen auszugeben.

public static void print_multiple_chars(char c, int count) {
    while (count > 0)
    {
        System.out.print(c);

count--;

jakobkogler

from itertools import product

disallow = 0
for move in product([0, 1, 2, 3], repeat=13):
        A, B, C, D = [move.count(i) for i in range(4)]
        if max(A, B, C) > D:
                disallow += 1

total = 4**13 - 1 # empty sequence
print('keep {} / {} move sequences'.format(total - disallow, total))