CoderZ.cc

Zurück   CoderZ.cc > Projekte der Nutzer > Wettbewerbe


 
Themen-Optionen Ansicht
16.05.2013, 18:55   #21
wieschoo (Offline)
Coderz Mitglied
 
Registriert seit: 14.09.2024
Beiträge: 80
Thanks: 11
Thanked 37 Times in 20 Posts
Standard

Sie liegen entweder (verglichen zu der aktuellen Wertigkeit) relativ dicht oder relativ entfernt zueinander.
Finde ich nicht überraschend. Es hätte mich erstaunt, wenn es eine gesetzmäßigkeit gäbe.

Aber du hast natürlich Recht:

Wäre halt interessant, ob es überhaupt möglich ist eine Aussage über die Lage möglich ist.
Immerhin gibt es ja gewisse Einschränkungen (Quersumme, letzte Ziffern,...).

Also, 200+ Zahlen in ca 22 stunden, hoch bis zum 24 stelligen Bereich.
Das ist recht gut. Ich habe mein Programm jetzt auf meinem vServer laufen. Da surrt wenigstens kein Lüfter mehr in der Nacht bei mir daheim

Die Frage ist, wie wir die Geschwindigkeit am Ende vergleichen wollen, da jeder andere Hardware verwendet.

Nichtsdestotrotz glaub ich, dass ich mal zum Thema Laufzeitoptimierung doch nochmal mit eigenen structs rumprobieren werd'.
Ich verwendet ttmath als BigInt Library. Die gängigen Funktionen sind drin und alle Sachen sind größtenteils als Templates implementiert. Hatte mal aufgeschnappt, dass da vieles zur Kompile-Zeit bereits optimiert wird.

Aus puren Spaß habe ich mal die Zahlensequenz in ein Midi File umgewandelt (siehe Anhang: zifferechtgoesmusic.rar)
Angehängte Grafiken
Dateityp: jpg verteilung.jpg (21,1 KB, 55x aufgerufen)
Angehängte Dateien
zifferechtgoesmusic.rar (808 Bytes, 6x aufgerufen)

Geändert von wieschoo (16.05.2024 um 23:58 Uhr)
  Mit Zitat antworten
26.05.2013, 17:34   #22
wieschoo (Offline)
Coderz Mitglied
 
Registriert seit: 14.09.2024
Beiträge: 80
Thanks: 11
Thanked 37 Times in 20 Posts
Standard Lösungen

siehe Anhang
Angehängte Dateien
loesungen.rar (484,6 KB, 6x aufgerufen)

Geändert von wieschoo (28.05.2024 um 00:12 Uhr)
  Mit Zitat antworten
The Following User Says Thank You to wieschoo For This Useful Post:
easysurfer (27.05.2024)
27.05.2013, 20:08   #23
easysurfer (Offline)
Third Level User
 
 
Registriert seit: 31.10.2024
Beiträge: 427
Thanks: 68
Thanked 243 Times in 131 Posts
Standard

Hatte leider den Einsendeschluss verpasst, daher hier noch meine Lösung + kleine Erklärung:
Ich verwende (genau wie nSinus-R) errechnete Quadzahlzahlen und splitte ebenfalls die letzte Zahl ab. Auch bei mir wird ein Array[iModResult]++ gemacht und im Anschluss geprüft.
Dabei wurde nach etwas Profiling klar, dass die ttMath-Lib mit großen Divisionen (und damit verbunden Mod-Operationen) richtig langsam wurde. Also habe ich zunächst noch die aktuelle Zahl in maximal 6 long (6* 4 Byte = 24 Byte) aufgespalten (mit einer Modulo-Operation 10^9). Danach wurden die longs durchgegangen und das ging dank "normaler" Rechenoperationen relativ fix.

Sourcecode: (ist nur der CalcManager interessant):
// CalcManager.h
#pragma once
typedef ttmath::UInt<4> MyBig; //<TTMATH_BITS(64), TTMATH_BITS(512)> MyBig;
class CalcManager
{
public:
    CalcManager(int ThreadNum);
    CalcManager(void);
    ~CalcManager(void);
    void DoCalc();
    BYTE aNumCount[10];
    MyBig llModulo;
    MyBig llRestN;
    MyBig llRestA;
    MyBig i;
    MyBig NumStart;
    MyBig NumEnd;
    int _ThreadNum;
    MyBig BigLongs[6];
    long Longs[6];
    void operator()() { DoCalc(); }
    bool CheckValids();
    bool CheckValidsInProgress();
    bool CheckNumber(MyBig llInput);
    long long GetTimeMs64();
};
// CalcManager.cpp
#include "CalcManager.h"
CalcManager::CalcManager(int ThreadNum)
{
    int sizeo = sizeof(long long);
    this->_ThreadNum = ThreadNum;
    this->llModulo = 0;
    this->llRestA = 0;
    this->llRestN = 0;
    this->NumStart = CALC_START + (ThreadNum * THREAD_NUMBERS);
    this->NumEnd = this->NumStart + THREAD_NUMBERS;
    for (int i = 0; i < 6 ; i++)
    {
        BigLongs[i] = 0x00;
        Longs[i] = 0x00;
    }
}
CalcManager::CalcManager(void)
{
}
CalcManager::~CalcManager(void)
{
}
void CalcManager::DoCalc()
{
    MyBig CounterCopy;
    MyBig ModuloOut;
    long long OldTime = GetTimeMs64();
    for (i = this->NumStart; i < this->NumEnd; i++)
    {
        ZeroMemory((BYTE*)&aNumCount[0],10);
        if (i == 71788112)
            int BREAK = 1337;
        if (CheckNumber(i*i))
            std::cout << "[" << this->_ThreadNum << "] i found: " << i.ToString() << " after " << ((GetTimeMs64()-OldTime)) << " ms [" << (GetTimeMs64()-OldTime)/1000/60 << ":" << ((GetTimeMs64()-OldTime)/1000)%60 << "] ||| Squared: " << (i*i).ToString(10) <<  std::endl;
        /*CounterCopy = i;
        CounterCopy.Div(1000000,&ModuloOut);
        if (ModuloOut == 0)
        {
            std::cout << "[" << this->_ThreadNum << "] Reached: " << i.ToString() << " after " << ((GetTimeMs64()-OldTime)) << " ms [" << (GetTimeMs64()-OldTime)/1000/60 << ":" << ((GetTimeMs64()-OldTime)/1000)%60 << "]" << std::endl;
        }*/
    }
    std::cout << "[" << this->_ThreadNum << "] Finished!" << std::endl;
}
bool CalcManager::CheckValids()
{
    for (int i = 1; i < 10; i++)
    {
        if (this->aNumCount[i] != 0x00 && this->aNumCount[i] != i)
            return false;
    }
    // Es kann vorkommen, dass sich eine 0 reinschleicht:
    std::string result;
    (i*i).ToString(result,10);
    if (strrchr(result.c_str(), '0'))
        return false;
    return true;
}
bool CalcManager::CheckValidsInProgress()
{
    for (int i = 1; i < 10; i++)
    {
        if (this->aNumCount[i] != 0x00 && this->aNumCount[i] > i)
            return false;
    }
    return true;
}
bool CalcManager::CheckNumber(MyBig llInput)
{
    /*llModulo = 10;
    llRestN = 0;
    llRestA = 0;
    MyBig llInputCopy = llInput;*/
    long long RestA = 0;
    long long RestN = 0;
    long long Modulo = 10;
    BYTE iLongCounter = 0;
    BYTE iLongSize = 0x00;
    // Wir teilen die große Zahl in Longs auf -> BigLongs (MyBig) werden mit Rest gefüllt
    do
    {
        llInput.Div(1000000000L, &BigLongs[iLongCounter]);
        iLongCounter++;
    }
    while (llInput.table[0] != 0);
    iLongSize = iLongCounter;
    iLongCounter = 0;
    // Wir füllen die "echten" Long Longs mit Werten
    for (int i = 0; i < iLongSize; i++)
    {
        Longs[i] = BigLongs[i].ToUInt();
    }
    // Wir gehen alle Long Longs durch und schauen was geht...
    for (int i = 0; i < iLongSize; i++)
    {
        while (RestN != Longs[i])
        {
            RestA = Longs[i] % Modulo;
            //llInputCopy = llInput;
            //llInputCopy.Div(llModulo, &llRestA);
            //llRestA -= llRestN;
            //llRestN = llRestA + llRestN;
            RestA -= RestN;
            RestN += RestA;
            if ( RestA == 0)
                return false;
            //llModulo *= 10;
            Modulo *= 10;
            //MyBig llModCopy = llModulo;
            //llModCopy.Div(100);
            //llRestA = llRestA / (llModulo / 100);
            RestA = RestA / (Modulo / 100);
            //aNumCount[llRestA.table[0]]++;
            aNumCount[RestA]++;
            if (!CheckValidsInProgress())
                return false;
        }
        RestA = 0;
        RestN = 0;
        Modulo = 10;
    }
    if (!CheckValids())
        return false;
    //DEBUGPrintNumCount();
    return true;
}
long long CalcManager::GetTimeMs64()
{
 /* Windows */
 FILETIME ft;
 LARGE_INTEGER li;
 /* Get the amount of 100 nano seconds intervals elapsed since January 1, 2025 (UTC) and copy it
  * to a LARGE_INTEGER structure. */
 GetSystemTimeAsFileTime(&ft);
 li.LowPart = ft.dwLowDateTime;
 li.HighPart = ft.dwHighDateTime;
 long long ret = li.QuadPart;
 ret -= 116444736000000000LL; /* Convert from file time to UNIX epoch time. */
 ret /= 10000; /* From 100 nano seconds (10^-7) to 1 millisecond (10^-3) intervals */
 return ret;
}
Ausgabe:
[0] i found: 1 after 0 ms [0:0] ||| Squared: 1
[0] i found: 20864888 after 17934 ms [0:17] ||| Squared: 435343551252544
[0] i found: 23309765 after 20033 ms [0:20] ||| Squared: 543345144355225
...
Greez
__________________
Gamehacking, Reversing and Security
  Mit Zitat antworten
The Following 2 Users Say Thank You to easysurfer For This Useful Post:
nSinus-R (28.05.2024), wieschoo (28.05.2024)
28.05.2013, 00:10   #24
wieschoo (Offline)
Coderz Mitglied
 
Registriert seit: 14.09.2024
Beiträge: 80
Thanks: 11
Thanked 37 Times in 20 Posts
Standard

Das war mir zu mühselig die Zahlen noch manuell zu zerlegen. Aber an sich ist ttmath eine hübsche Sache, wenn ich den Aufwand gegenüber gmp oder mpir vergleiche.

Ich packe das noch dann ins Archiv
  Mit Zitat antworten


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 
Themen-Optionen
Ansicht

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.

Gehe zu


Alle Zeitangaben in WEZ +2. Es ist jetzt 05:20 Uhr.

Powered by vBulletin®
Copyright ©2008 - 2013
Template-Modifikationen durch TMS