Այս հոդվածի համար ես ընտրել եմ պատկերի մակերեսի հաշվման թվային մի եղանակ, որ ավելի հայտնի է “Մոնտե-Կառլոյի մեթոդ” անվանբ։ C, Java, Go, Common Lisp և C++11 լեզուներով ես կներկայացնեմ թվային ինտեգրման այս եղանակի իրականացումը։
Ենթադրենք տրված է մի P պատկեր, որի մակերեսն ուզում ենք հաշվել։ Ընդգրկենք այդ պատկերը a կողմով A քառակուսու մեջ, որի ներքևի ձախ անկյունը տեղադրված է կոորդինատների սկզբնակետում։ Պատահականորեն ընտրենք քառակուսու մեջ ընկած N կետեր և հաշվենք, թե դրանցից քանիսն են պատկանում P պատկերին. նշանակենք այդ քանակը n0։ Ըստ Մոնտե-Կառլոյի մեթոդի, P պատկերի մակերեսի հարաբերությունը A քառակուսու մակերեսին պետք է հավասար լինի N-ի արաբերությանը n0-ին։
Ծրագրավորման տեսակետից, պետք է սահմանել մի ֆունկցիա, որ ստանում է P պատկերը բնութագրող ֆունկցիան, A քառակուսու կողը՝ a, և պատահականորեն ընտրվող կետերի քանակը N, ապա հաշվարկում և վերադարձնում է պատկերի մակերեսը։ Պատկերը բնութագրող ֆունկցիան պետք է պատասխանի արդյո՞ք տրված կետն ընկած է պատկերի վրա, թե՝ ոչ։
Որպես օրինակ վերցնենք f(x)=x2 ֆունկցիան և հաշվենք նրա ինտեգրալը [-2;2] միջակայքում։ Նախ հաշվենք մաթեմատիկական եղանակով.
այս արժեքը կարելի է օգտագործել նաև որպես ծրագրերի ստուգման միջոց։
Ինչպես ասվեց վերևում, Մոնտե-Կառլոյի մեթոդի կիրառման համար ընդգրկող քառակուսին պետք է ընկած լինի առաջին քառորդում (սա, իհարկե, արված է պարզության համար, պարզ է որ կարելի է վերցնել կամայական քառակուսի կամ ուղղանկյուն, կամ մի այլ պատկեր, որի մակերեսը հեշտ է հաշվել)։ Դրա համար տեղաշարժենք f(x)=x2 ֆունկցիայի գրաֆիկն այնպես, որ [-2;2] միջակայքում ընկած հատվածև տեղափոխվի առաջին քառորդ։ Այդ նոր ֆունկցիան կարտահայտվի f(x)=(2-x)2 բանաձևով, և հենց այս բանաձևն էլ կօգտագործվի որպես բնութագրող ֆունկցիա։
Սկսենք C լեզվից։ Պատահական թվերը գեներացվում են rand
ֆունկցիայով, որը վերադարձնում է [0; RAND_MAX)
միջակայքի պատահական ամբողջ թիվ։ [0; a)
միջակայքի պատահական թվեր ստանալու համար սահմանված է հետևյալ ֆունկցիան.
/**/ double random(double s) { return s * ((double)rand() / RAND_MAX); }
C լեզվում բարձր կարգի ֆունկցիաներ չկան և բնութագրող ֆունկցիան պետք է փոխանցել ցուցիչի տեսքով։
/**/ double monteCarloMethod(int(*f)(double,double), double a, int n) { int no = 0; while( n-- > 0 ) if( f( random(a), random(a) ) ) ++no; return a * a * no / n; }
Բնութագրող ֆունկցիայի սահմանումը նույնպես պարզ է.
/**/ int parabola(double x, double y) { double e = 2.0 - x; return e * e > y; }
main
ֆունկցիան պարզապես կանչում է monteCarloMethod
ֆունկցիան, նրան փոխանցելով պարաբոլը բնութագրող ֆունկցիայի հասցեն, ընդգրկող քառակուսու կողը՝ 4, և պատահական ընտրվող կետերի քանակը։
/**/ int main() { srand(time(0)); double res = monteCarloMethod(¶bola, 4.0, 10000); printf("%f\n", res); return 0; }
Java լեզվով խնդրի լուծումը ներկայացնեմ որպես ամբողջական ֆայլ, որի մեջ գրված են անհրաժեշտ մեկնաբանությունները։
package montecarlo; import java.util.Random; public class MonteCarlo { // պատահական թվերի գեներատոր private static Random generator = new Random(); // Այս ինտերֆեյսը սահմանված է բնութագրող ֆունկցիաների համար։ // check ֆունկցիայի իրականացումը կպարունակի բուն բնութագրիչը։ private interface Characteristic { boolean check(double x, double y); } // Characteristic ինտերֆեյսի իրականացումն է քառակուսային ֆունկցիայի համար։ // Այս դասի նմուշը կոգտագործենք հաշվարկների համար։ private class Quadratic implements Characteristic { @Override public boolean check(double x, double y) { double e = 2.0 - x; return e * e > y; } } // Պատահական թվի մասշտաբավորում մեր միջակայքի համար։ private static double rnd(double a) { return a * generator.nextDouble(); } // Մոնտե-Կառլոյի մեթոդը։ private static double monteCarloMethod(Characteristic f, double a, int n) { int no = 0; // պատկերի ներսում ընկած թվերը for( int i = 0; i < n; ++i ) // բնութագրիչի կիրառում պատահական կոորդինատների համար if( f.check(rnd(a), rnd(a)) ) ++no; // մակերեսի հաշվարկ return a * a * no / n; } /**/ public static void main(String[] args) { Quadratic f = (new MonteCarlo()).new Quadratic(); double res = monteCarloMethod(f, 4, 1000); System.out.println(res); } }
Go լեզվով ծրագիրն արդեն բավականին կոմպակտ է։ Նախ սահմանենք բնութագրիչ ֆունկցիայի տիպը։
type XYPredicate func(float64,float64) bool
Բուն մեթոդն ունի ահա այսպիս տեսք.
// Monte-Carlo method. func monteCarloMethod(f XYPredicate, a float64, n int) float64 { // պատկերի ներսում ընկած կետերի քանակը var no int for i := 0; i < n; i++ { // պատահական կետի կոորդինատներ x := a * rand.Float64() y := a * rand.Float64() // բնութագրիչի ստուգում if f(x,y) { no++ } } // մակերեսի հաշվարկ return (float64(no) * a * a) / float64(n) }
Պարաբոլի բնութագրող ֆունկցիան։
func parabola(x, y float64) bool { e := 2.0 - x return e * e > y }
Եվ կիրառումը.
func main() { k := monteCarloMethod(parabola, 4.0, 10000) fmt.Println(k) }
Common Lisp լեզվով իրականացումն իհարկե ամենագեղեցիկն է։ Միայն loop մակրոսի մեկ կիրառությամբ ծրագրավորված է ալգորիթմը։ Իմ կարծիքով, արտահայտված է նաև սեմանտիկան.
(defun monte-carlo-method (f a &optional (n 100)) (loop repeat n ; կրկնել n անգամ with no = 0 ; պատկերի կետերի քանակը when (funcall f (random (float a)) (random (float a))) ; պայմանի ստուգում do (incf no) ; կետերի քանակի վերահաշվարկ finally (return (/ (float (* a a no)) n))))
Պարաբոլը բնութագրող ֆունկցիան է։
(defun parabola (x y) (let ((e (- 2 x))) (> (* e e) y)))
Արժեքի հաշվարկ և արտածում։
(print (monte-carlo-method #'parabola 4 10000))
Եվ վերջապես, C++11 իրականացումը։
/**/ double monteCarloMethod( std::function<bool(double,double)> f, double a, unsigned int n ) { std::random_device dev; std::default_random_engine eng(dev()); std::uniform_real_distribution<double> distr(0.0, a); // unsigned int no(0); for( unsigned int i = 0; i < n; ++i ) if( f( distr(eng), distr(eng) ) ) ++no; // return a * a * no / n; }
/**/ bool parabola(double x, double y) { double e(2.0 - x); return e * e > y; }
/**/ int main() { std::cout << monteCarloMethod(parabola, 4.0, 10000) << std::endl ; return 0; }
Բացատրությունները ապագայում 🙂
Շնորհակալություն, լավ նյութ է
Այ հիանում եմ ․․․ Go, Common Lisp ... Վերջապես ․․․ Կար ժամանակ երբ մենակ եփվում էի PLAN9/Inferno , մեկ-մեկ էլ QNX ի գրկում․ ՈՒ մեկը չկար բան քննարկեի ։-) Հետաքրքիր ա, Erlang ը կա՞ էս շարքում։ Հ․Գ․ Հուսով եմ երևում ա, թե մտքիս թելը ուր ա գնում
Շնորհակալություն դրական արձագանքի համար :) Անկեղծ ասած, վաղուց պլանավորում եմ ծանոթանալ Erlang-ի հետ, բայց ինչ-որ չի ստացվում (ժամանակի տեսակետից)։ Հիմա ամբողջ ազատ ժամանակս կլանում է Common Lisp լեզվի մասին հայերեն գիրքը, որ նախաձեռներլ եմ մի քանի ամիս առաջ, և Go լեզվի նախնական ուսումնասիրությունը։ Երևի առաջիկայում այս կայքում կհայտնվեն առավելապես Common Lisp, Go, C++ լեզուներին առնչվող հոդվածներ։