Mathematics / Mathematik / Matemática

Mathematics / Mathematik / Matemática

Posts 1-7 of 7
  • Roman Doubrava
    Roman Doubrava    Premium Member
    The company name is only visible to registered members.
    Generische Algorithmen für ein neues Komprimierungsverfahren / Generic algorithms for looseless compression
    Hallo zusammen,

    seit geraumer Zeit beschäftige ich mich privat mit der Entwicklung eines Komprimierungsverfahrens und hänge im Moment an einer Stelle an der mein Wissen der Mathematik nicht mehr ausreicht, ich brauche
    dringend Hilfe oder zumindest ein Statement über die Machbarkeit meines Vorhabens.

    Zum Problem:

    Ich suche eine Art Meta Algorithmus der wiederrum andere Algorithmen generieren kann und sie im Anschluss optimiert, oder zumindest eine hinreichende Optimierung vornimmt.

    Die Funktionsweise:

    Eine Zahl "y" soll soll über den Meta Algorithmus zerlegt werden in
    eine Funktion der Art: y = f1(x1) + f2(x2) * f3(x3) / f4(x4) .... fn(xn)

    Dabei sind die Operatoren zwischen den einzelnen (f1....fn) Unter Funktioen (+,*,-) egal, d.h. die Ausprägung der Zerlegten Funktion muss einfach die Gleichnug erfüllen.

    Im Optimierungsschritt ist zu Beachten das die Anzahl der Operanden minimiert wird und als zweites Kriterium die Anzahl der Nachkommastellen der einzelnen (x1....xn) Operanden ebenfalls minimiert wird.

    Ausgagssituation: y = 100
    Ergebniss: 100 = 4*4! + 2*2!

    Der Meta Algorithmus soll mehrere Lösungsfunktionen generieren und nach der Optimierung die Funktion mit der geringsten Anzahl an Operanden und der geringsten Anzahl an Nachkommastellen der Oparanden finden.

    Vielen Dank für jede Hilfe und jeden Denkanstoss...
    ______________________________________________________________________

    Hi ppl,

    since some years i am developing a new way of a looseless data compression,
    i am on a point where my knowledge in math and numerics give up, so i need
    help or just a statement if my problem is possible to solve.

    Problem:

    I search a kind of meta algorithm which is able to generate other algorithms,
    optimize them and meet the following conditions.

    The function of the algorithm in detail:

    For a number "y" the algorithm have to genarte solutions like:
    y = f1(x1) + f2(x2) * f3(x3) / f4(x4) .... fn(xn)

    Condition 1: The Operators(+,*,-) between and in the underlaying operand functions(f1....fn)
    are arbitrary, but the solution have to stay valid.

    Condition 2: After the first optimization step the amount of the underlaying
    functions(f1....fn) have to shrink, the solution have to stay valid.

    Condition 3: After the second optimization the mantissa of each (x1....xn)
    Values have to shrink against zero.

    The meta algorithm should generate many solutions and after the optimization
    steps only the soultion with the lowest amount of operands(f1...fn) and lowest
    amount of their mantissa of each (x1....xn)

    Example: y = 100
    One optimized Solution,mantissa = 0: 100 = 4*4.0! + 2*2.0!

    Thanks for any help or idea....

    --
    Thread was moved from "Mathematical Curiosities" to "Numerics"
    This post was changed on 27 Sep 2006 at 08:37 am by Dr. Dirk Kehrwald .
    • 26 Sep 2006, 1:54 pm
  • Tillmann Miltzow
    Tillmann Miltzow
    The company name is only visible to registered members.
    Re: Generische Algorithmen für ein neues Komprimierungsverfahren / Generic algorithms for looseless compression
    Hi

    I do not undrestand the Problem.

    f1(x1) := y
    fi(xi) := 0 forall i>1
    and ever use +

    Does this help you??

    Tillmann
    • 26 Sep 2006, 9:58 pm
  • Post visible to registered members
  • Post visible to registered members
  • Roman Doubrava
    Roman Doubrava    Premium Member
    The company name is only visible to registered members.
    Re^4: Generische Algorithmen für ein neues Komprimierungsverfahren / Generic algorithms for looseless compression
    "You know to decompose large numbers into a product of a number multiplied by it's factor. "

    Yes it's exactly my idea, but it doesn't matter if it's a product or a sum or a sub function e.g. gamma(x)

    I try to construct a string sequence independend algorithm, which works in the decimal numeric system, not hex or bitwise.

    If i look at the gamma(x) function, thats indeed one good example for one f1(x) operand in the whole meta-algorithm, it can represent all numbers and reverse them. The problem here are the mantissa lengths. Now we could try to split our Y in more gama(x) constants with lower mantissa lengths. It exist one optimum of the amount of operands and mantissa lengths in this simple equation.

    Y = gamma(x1) * gamma(x2) ^ gamma(x3) ....... f(xn)
    x1...xn: Should have the same shortest mantissa length

    Now i am searching for other functions like gamma(x) which could be
    !combined! with gamma(x) to complete the Y with lower amount of function
    operands(x1....xn).

    Sources: http://mathworld.wolfram.com/GammaFunction.html

    My dream is:

    A database full of mathematical Functions which can be processed online, the server which is holding that database generate and learn new functions. The compression clients hold a part of that database and in some cases they send part string sequences(as decimal numbers) to the server to look up for new efficient functions. After each compression each client updates the server whith the new generated or used functions. The database grow with each client compression and precalculate new functions.

    I implemented this kind with java's BigDecimal datatype, but my database is in prototype state, i have to implement analytics which do something like a scoring on each function, to speed up the look up
    depending on the string sequence.

    Thx for any help....
    • 27 Sep 2006, 11:30 am
  • Post visible to registered members
  • Dietrich Brunn
    Dietrich Brunn
    The company name is only visible to registered members.
    Re^5: Generische Algorithmen für ein neues Komprimierungsverfahren / Generic algorithms for looseless compression
    Hi Roman

    My dream is:
    A database full of mathematical Functions which can be processed online, the server which is holding that database generate and learn new functions. The compression clients hold a part of that database and in some cases they send part string sequences(as decimal numbers) to the server to look up for new efficient functions. After each compression each client updates the server with the new generated or used functions. The database grow with each client compression and precalculate new functions.
    This sounds like a very challenging task. I'm no expert on compression and theoretical computer science, but as far I know there two important points:
    1) To develop a usable algorithm, the algorithmic complexity shouldn't be NP-hard, i.e. the demand of computational resources should not increase exponentially with the length of the data, which is to be compressed. As far I know, this is key problem for data compression. See:
    http://en.wikipedia.org/wiki/Computational_complexity_theory
    For your approach, I would guess it is np-hard (but I'm not sure).

    2) The focus lies not only how to compress single words (in your case numbers) efficiently, but those words are compressed highly that occur frequently and those which don't occur often are not compressed as much. A simple example is the morse code, where the frequent letter e is only a single dot and the uncommon letter q (- - -) are quite long. A more formal approach is the use of "information entropy", quoting http://en.wikipedia.org/wiki/Information_entropy :
    "Entropy effectively bounds the performance of the strongest lossless (or nearly lossless) compression possible, which can be realized in theory by using the typical set or in practice using Huffman, Lempel-Ziv or arithmetic coding. The performance of existing data compression algorithms is often used as a rough estimate of the entropy of a block of data."

    Cheers, dietrich
    • 27 Sep 2006, 1:33 pm