Legnagyobb közös osztó-keresés


Hát ez nem pont egy technikai téma, inkább matek, de arra gondoltam, kiposztolom ide, hátha valakinek van ötlete. Szóval úgy néz ki, lassan szükségem lesz egy olyan algoritmusra, ami egy adott halmaznak megadja a legnagyobb közös osztóját. Ugye ha egész számokról van szó, akkor ez egy elég triviális probléma. A gond az, hogy nekem valós számokra kell elvégeznem a dolgot, és igazából nem is a szigorúan vett "legnagyobb közös osztóra" van szükségem (két irracionális szám esetén például lehet, hogy nincs is közös valós osztójuk), hanem valahogy arra a valós számra, ami egy egészséges egyensúlyt ad a következő két feltételre:

  1. Egy adott (valós) számhalmaz elemeit elosztva ezzel a bizonyos számmal a maradékok legyenek "kicsik".
  2. A halmaz elemeit ezzel a bizonyos számmal elosztva az eredmények legyenek "minél közelebb" olyan racionális számokhoz, amelyeknek a nevezője "minél kisebb".

És plusz pontért még egy kritérium:

  • A számhalmaz minden eleméhez lehessen rendelni egy "súlyparamétert", ami azt mutatja, hogy mennyire "gáz", ha ezt a bizonyos legnagyobb közös osztót ennek a számnak az "ignorálásával" határozzuk meg.

A konkrét megoldandó probléma az, hogy adott egy formáns-halmaz (vagyis: egy adott hangról készített "FFT-szkeccs", vagyis nem a teljes FFT kép, hanem csak a legjellemzőbb frekvenciák és a hozzájuk tartozó amplitúdók, mint "súlyfaktorok") és ezekből az adatokból meg kell határoznom, hogy milyen hang szól (pontosabban, hogy a mintavételezett spektrumnak mi az "alaphangja"). Az alaphang az a frekvencia, amivel a "legegyszerűbben" magyarázható a spektrum többi tagja.

Utóbbi alatt a következőt értem: ideális esetben egy (hangszer)hang spektruma modellezhető úgy, mint egy f0 alapfrekvencia és ennek fn=nf0 felhangjainak halmaza (n egész, vagy legalábbis olyan racionális szám, aminek a nevezője kellően kicsi). A gyakorlatban általában a mérési hibák, az adatfeldolgozás során bevitt egyéb hibák (pl. FFT-ablakolási problémák stb.) a környezet és a hangszerek nemlinearitása miatt ez a modell nem teljesen helytálló. Sajnos az irodalomban csak olyan képleteket találok alaphangbecslésre, amik erősen "mérnöki" jellegűek (pl. most olvastam egyet, ahol bizonyos hibákat ad össze bizonyos együtthatókkal, majd a képlet után közli, hogy "X és Y javaslata alapján az együtthatók legjobb értékei" majd jön egy rakás szám mindenféle indoklás nélkül), és valahogy nincs gusztusom ilyesmivel dolgozni, ezért gondoltam, hogy valamit összeütök magamnak, aminek egy ilyen "legnagyobb közös valós osztó keresés" lenne az első lépése.

Tagek:
 
Utoljára módosította SAdam 2010.VIII.30 11:57-n; 2 hozzászólás;
Bejegyzés módosítása | PermaLink
Votes disabled.