<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Aiswarya Prakasan on Medium]]></title>
        <description><![CDATA[Stories by Aiswarya Prakasan on Medium]]></description>
        <link>https://medium.com/@aiswaryamathur?source=rss-f6b07002c404------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*PIK6tEJxF5zYedn0dbNV-w.jpeg</url>
            <title>Stories by Aiswarya Prakasan on Medium</title>
            <link>https://medium.com/@aiswaryamathur?source=rss-f6b07002c404------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 07:21:01 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@aiswaryamathur/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Every developer should know the deeper nuances in these terms.]]></title>
            <link>https://medium.com/@aiswaryamathur/every-developer-should-know-the-deeper-nuances-in-these-terms-4aa174966ebd?source=rss-f6b07002c404------2</link>
            <guid isPermaLink="false">https://medium.com/p/4aa174966ebd</guid>
            <category><![CDATA[engineering]]></category>
            <category><![CDATA[reactive-programming]]></category>
            <category><![CDATA[concurrent-programming]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Aiswarya Prakasan]]></dc:creator>
            <pubDate>Mon, 06 Jul 2020 08:12:18 GMT</pubDate>
            <atom:updated>2020-07-06T08:12:18.066Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Make sure you are using the right words when you say a particular framework is “asynchronous”, “non-blocking” and “event-driven”.</em></p><p>What does it mean when your colleague describes something as non-blocking, asynchronous I/O. Is it possible to have a blocking, asynchronous I/O? If not, does non-blocking and asynchronous mean the same thing? In this post, I will explain the right meaning and usage of these (and many other) commonly used (and often misused) software engineering terms.</p><p><strong>Concurrent vs Parallel execution</strong><br>Concurrent execution — Overlapped execution or time slicing. Concurrency is a programming property that can happen even for a single core machine.</p><p>Parallelism — Simultaneous execution. This is a property of the execution hardware where tasks actually proceed simultaneously.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hAjcQ51byOCsKkbqUeN3_Q.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/966/1*eurac67AV4GYDN9ws0Nzpw.png" /></figure><p><strong>Sync vs Async<br></strong>Synchronous — In case of synchronous operation, the party initiating the operation has to wait until the operation completes.</p><p>Asynchronous — In asynchronous operation, the initiator does not need to wait for the operation to complete. It can proceed to its next steps without waiting for a result from the other party. The completion of the operation can be later detected through some other mechanism. This concept can be applied to other areas besides programming. Email is an example of asynchronous communication whereas a phone conversation is synchronous.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/830/1*Ui_hbErgHZvm9jMKZiLWXA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/818/1*4ue_spcv9K_Uy9dLn0WiPw.png" /></figure><p><strong>Blocking vs Non-blocking<br></strong>This is a programming concept and more related to how you write code (unlike sync vs async). If a function call returns a value immediately, it is called <strong><em>non-blocking</em></strong>. In some cases like I/O, the result of logical completion of a function is not available immediately. However, it returns the reference to a place-holder where value will become available later. For eg, Java Future. The following function returns immediately even though the value is available only after 10 seconds.</p><pre>public Future&lt;Integer&gt; calculate(Integer input) {                         return executor.submit(() -&gt; {             <br>               Thread.sleep(10000);             <br>               return input * input;         <br>        });     <br>}</pre><p>An async function call cannot be blocking.</p><p>Non-blocking and asynchronous may or may not mean the same thing depending on context. While email communication is asynchronous, it doesn’t really make sense to call email as non-blocking.</p><p><strong>Imperative vs declarative programming style</strong></p><p>Declarative programming is a programming paradigm that expresses the logic of a computation(What to) without describing its control flow(How to). For example SQL commands.</p><p>Imperative programming is a programming paradigm that describes computation in terms of statements that change a program state.</p><p>The following example loops through the numbers 1 through 10, and finds the even numbers.</p><pre>List&lt;Integer&gt; numbersOneThroughTen = new ArrayList&lt;&gt;(Arrays.<em>asList</em>(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));</pre><pre>//With imperative programming, we&#39;d step through this, and decide //what we want:</pre><pre>List&lt;Integer&gt; evenNumbers = new ArrayList&lt;&gt;();<br>for (Integer eachValue : numbersOneThroughTen) {<br>    if (eachValue % 2 == 0) {<br>        evenNumbers.add(eachValue);<br>    }<br>}</pre><pre>//The following code uses declarative programming to accomplish the //same thing.<br>// Here, we&#39;re saying &quot;Give us everything where it&#39;s odd&quot;</pre><pre>evenNumbers = numbersOneThroughTen.stream().filter(num -&gt; num % 2 == 0)<br>              .collect(Collectors.<em>toList</em>());</pre><p>Note : This is an abstract concept. In the above example, you can go further to say that we are not given the actual implementation of ‘foreach’, so in a certain sense it is describing “What to” and not “How to”. Every programming style lies somewhere on the spectrum from purely imperative to purely declarative. Functional Programming is more declarative than procedural programming.</p><p><strong>Functional Programming<br></strong>A programming paradigm where programs are constructed by applying and composing functions. In functional programming, functions are treated as first-class citizens, meaning that they can be bound to names (including local identifiers), passed as arguments, and returned from other functions, just as any other data type can. This allows programs to be written in a declarative and composable style, where small functions are combined to create larger functions and programs. Purely functional programming is a subset of functional programming where all functions are pure functions. I will be writing another detailed blog post on functional programming.</p><p><strong>Event-driven or message-based architecture<br></strong> An <em>event</em> is a significant change in the state of the system. For example, when a consumer purchases a car, the car’s state changes from “for sale” to “sold”. A car dealer’s system architecture may treat this state change as an event whose occurrence can be made known to other applications within the architecture. Strictly speaking, an event cannot travel, it just occurs. What is emitted, processed and propagated is actually a notification of the event — in the form of an all-text message. In an event-driven system, different participating components communicate via asynchronous messages.</p><p><strong>Reactive system vs Reactive programming<br></strong>A <em>reactive system</em> is a program whose architecture allows it to react to changes in its runtime environments. Properties that reactive systems should have are formalized in the Reactive Manifesto (<a href="http://www.reactivemanifesto.org/">http://www.reactivemanifesto.org</a>). Three of these properties can be summarized as responsive, resilient, and elastic.</p><p><em>Responsive</em> means that a reactive system can respond to inputs in real time rather delaying a simple query because the system is processing a big job for someone else.</p><p><em>Resilient</em> means that a system generally doesn’t fail because one component fails; a broken network link shouldn’t affect queries that don’t involve that link, and queries to an unresponsive component can be rerouted to an alternative component.</p><p><em>Elastic</em> means that a system can adjust to changes in its workload and continue to execute efficiently. As you might dynamically reallocate staff in a bar between serving food and serving drinks so that wait times in both lines are similar, you might adjust the number of worker threads associated with various software services so that no worker is idle while ensuring that each queue continues to be processed.</p><p>Clearly, these properties can be achieved in many ways, but one main approach is to use <em>reactive programming</em> style.</p><p>Reactive programming is programming with events represented as asynchronous messages (as in event-driven architecture). These messages are often modelled as data streams. For eg, in a web application your typical click events can be modelled as a stream of data, on which you can observe and do some side effects. You are able to create data streams of anything, not just from click and hover events. Streams are cheap and ubiquitous, anything can be a stream: variables, user inputs, properties, caches, data structures, etc. For example, your Twitter feed is a data stream in the same fashion that click events are. You can listen to that stream and react accordingly.</p><p>A stream can be used as an input to another one. Even multiple streams can be used as inputs to another stream. You can <em>merge</em> two streams. You can <em>filter</em> a stream to get another one that has only those events you are interested in. You can <em>map</em> data values from one stream to another new one.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4aa174966ebd" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Life lessons from people smarter than me.]]></title>
            <link>https://medium.com/@aiswaryamathur/life-lessons-from-people-smarter-than-me-5ae90fbd8c61?source=rss-f6b07002c404------2</link>
            <guid isPermaLink="false">https://medium.com/p/5ae90fbd8c61</guid>
            <category><![CDATA[philosophy]]></category>
            <category><![CDATA[notes-to-self]]></category>
            <category><![CDATA[life-lessons]]></category>
            <category><![CDATA[naval-ravikant]]></category>
            <category><![CDATA[happiness]]></category>
            <dc:creator><![CDATA[Aiswarya Prakasan]]></dc:creator>
            <pubDate>Wed, 01 Jul 2020 16:57:42 GMT</pubDate>
            <atom:updated>2020-07-20T12:58:37.019Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Key takeaways (in my own words) from a conversation between Naval Ravikant and Shane Parrish.</em></p><p>I recently came across a great podcast episode — where Shane Parrish [the creator of podcast — <a href="https://fs.blog/knowledge-project/">The Knowledge Project</a>] interviews <a href="https://twitter.com/naval">Naval</a> Ravikant. For the uninitiated, Naval Ravikant is the co-founder and CEO of AngelList. He has invested in several early stage start-ups including Uber, Twitter, Foursquare and Yammer. He is a clear thinker and a great communicator. Lately, I’ve been fascinated by his philosophies and world -view. I would recommend everyone to listen to the whole thing — <a href="https://www.youtube.com/watch?v=mGY2To_HW98">https://www.youtube.com/watch?v=mGY2To_HW98</a></p><p>I have made some notes, primarily for my reference. Feel free to skim through and comment.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/768/1*iTjPwqj0fZb2YaY0PA5RHQ.jpeg" /></figure><p><strong>On Books</strong> : Spending time and money on books is worthwhile — even if you don’t read it cover-to-cover. It is better to read books like we read blogs — just consume what appeals to you and leave the rest. It is okay to skim through and only read the parts that are interesting to you. It is okay to be distracted and jump around. Business and self-help category of books generally have one good idea and 100s of pages with lots of anecdotes and examples. You don’t need to read the whole book, just get the idea and move on. Very few people actually read and finish a book. Reading an hour a day will make a huge difference. It will help you in a big way. Don’t read for social approval — read the books that make sense to you. Many people read the best-sellers to fit in with the herd. If you are reading to be cool you are doing it wrong. Read contrarian view-points too — things that you disagree with — so that you can understand where their point of view comes from. However, authors who state lies and delusions as facts are serious red flags. Drop them immediately. Consider re-reading the books you like, to solidify ideas.</p><p><strong>On Habits </strong>: Habits are hugely important for efficient functioning. All of us have lots of habits. Even the things we don’t typically think of as habits — how we think, how we judge people, our mood, our happiness levels, how productive we are, our thought patterns — these are also habits. We picked up some patterns through our lives and repeated it enough number of times to tie our identity with it. It is important to isolate and recognise helpful and unhelpful habits. Un-condition yourself of the unhelpful/harmful habits. It is absolutely possible to break habits. It’s hard, but it is possible. Make your habits deliberate and not accidents.</p><p><strong>On Happiness, meditation and the monkey-mind : </strong>It’s important to explore what happiness means to you — it has a very personal definition for everyone — it could be a feeling of contentment, or flow state or simply feeling peaceful. You need to do serious internal reflection to understand what happiness means to you. Serious reflection is a lonely pursuit. If you sit by yourself and try to observe the mind you’ll see a continuous stream of unstoppable thinking — what needs to be done next, judgements on people and things around, things that have happened in the past or could happen in the future and so on. To stop this non-stop chat is a hard task. As a first step, you need to, sort-of, put your brain in debug mode and observe what is going on.</p><p>Try to live more in the child-mode — driven by the curiosity of present more than anything else. This will help you to build a mindset required to focus deeply. The ability to singularly focus is related to your ability to lose yourself and it ironically makes you more effective. Mind itself is a muscle and it can be trained and conditioned — just that it has been haphazardly conditioned by the events in our life. Look at it with awareness and intent to start understanding your emotions and feelings and you can start reconfiguring it into what you want. It would be so masterful if you could actually control your mood — like now I want to be in curious state and switch to the curious state. Or that you want to be in the morning state and go to that state.</p><p><strong>On Values</strong> — Values are the list of things you won’t compromise on, honesty and long-term thinking for example. Take some time and figure out your foundational values. Radical honesty is one of Naval’s core values. To him it means think what you say and say what you think (without being deliberately hurtful). When you lie to others you start believing that at some level, you sort of lie to yourself and that disconnects you with reality. Seeing truth as it is, is important. Ethics and values are fundamental because you cannot hide from yourself. Whatever you do has an impact on your psyche. Your actions become a part of your character. Be an honest person. Otherwise, you will lose your self esteem. You should be able to respect yourself. It is very important. Being ethical is profitable in the long term. Short term sacrifice has long term benefits. “Easy choices, hard life. Hard choices, easy life.” All benefits in life comes from compound interest. Stick with things that matter, for the long term.</p><p><strong>On Criticism</strong> — Praise specifically (praise the person), criticise generally (criticise the general approach.)</p><p><strong>On politics</strong> — Creating identities and labels locks you up and keeps you from seeing the truth. For eg, identifying as a libertarian. You will not be able to accept any point of view that is seemingly at odds with your predefined identity. If all of your beliefs line up into neat little bundles with tags, you should be suspicious because they’ve been pre-packaged and put together.</p><p><strong>On current education system </strong>— It is completely obsolete. If you have the desire to learn you can learn anything. Tomorrow is all about customised education.</p><p><strong>On original thinking and success</strong> — Smartest and the most successful people often started out as losers. If you view yourself as a loser, as someone who has been cast out by the society, you stop trying to fit in and carve out your own path and develop original thinking.</p><p><strong>On decision-making </strong>— It is everything. If you make more right decisions than others, you are very precious. If you can be more right and more rational, then you are going to get non-linear gains. Mental models help you think and reason about things. Predicting the future is hard. You cannot say what is going to work — being successful is about avoiding incorrect judgement as much as possible. Develop mental-models that help you make better decisions. Set up systems, not goals. Build systems to create an environment around so that you can be right a lot. Individual decisions don’t matter that much, your systems should be strong.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5ae90fbd8c61" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How did we become a generation of mentally ill people?]]></title>
            <link>https://medium.com/@aiswaryamathur/are-we-a-generation-of-mentally-ill-people-9af42a917530?source=rss-f6b07002c404------2</link>
            <guid isPermaLink="false">https://medium.com/p/9af42a917530</guid>
            <category><![CDATA[depression]]></category>
            <category><![CDATA[mental-health]]></category>
            <category><![CDATA[social-change]]></category>
            <category><![CDATA[mental-illness]]></category>
            <category><![CDATA[society]]></category>
            <dc:creator><![CDATA[Aiswarya Prakasan]]></dc:creator>
            <pubDate>Tue, 11 Apr 2017 02:31:58 GMT</pubDate>
            <atom:updated>2017-04-14T02:27:12.297Z</atom:updated>
            <content:encoded><![CDATA[<p><em>“An analysis of why depression is on the rise.”</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*S5x5zyaBkXZVtp6fvg1oNg.png" /></figure><p>Mental health has been somewhat of a touchy topic .We don’t like to talk about it much. And when we do, we don’t talk about it very well — it shows in the terms we use to describe the mentally ill (crazy, psycho, retarded for instance) and the caricatured stereotypes portrayed in the media.</p><p>However, in the recent past, there has been a growing presence of a particular kind of mental illness in popular culture — depression. Several celebrities have come out in the open about their experiences with Major Depressive Disorder (MDD or depression). It looks like we can now have a public discussion regarding the once-taboo-topic without its victims feeling humiliated.</p><p>With this trend, some genuinely disturbing statistics have come to light. The World Health Organisation (WHO) estimates that worldwide depression is the leading cause of disability for people in midlife and for women of all ages. Depression is diagnosed in about 40% of patients who see a psychiatrist. This percentage has doubled just in the last 20 years .Consumption of antidepressants has soared since 1990. By 2000, antidepressants were the best-selling prescription drugs of any type! Yet, studies suggest that there are vast numbers of untreated depressed people. In the past, depression was a major psychiatric illness that was not very common. But according to current estimates, one in every ten people is likely to have had depression at some point in their life.</p><p>The sharp increase in the number of cases of MDD is ironic in some sense. Statistically speaking, we are now in the best, most peaceful time in our species’ existence. If you didn’t know who you were to be born as, I’d argue this is the best time to be born — thanks to the global decline in violence and discrimination, great advancement in science, technology and medicine, better education opportunities, lower mortality and poverty rates. How then, did we get ourselves into this bizarre epidemic of mental disorder?</p><p>Turns out, it may not be an epidemic at all. The sudden rise in the rate of MDD can be explained by a change in its diagnosis by the Diagnostic and Statistical Manual of the American Psychiatric Association (DSM-III) in 1980. These changes were made in an effort to make the criteria for depression (and other mental disorders) uniform and easily quantifiable. In the past, only symptoms that were “excessive” and “inexplicable” were considered to be signs of depressive disorder. This made the diagnosis somewhat subjective. Now however, someone who has three to five symptoms out of a list of nine, that include — depressed mood, loss of interest in usual activities, insomnia, fatigue, lessened appetite, an inability to concentrate and similar symptoms — for as brief a period as two weeks is considered to have MDD (Major Depressive Disorder). The problem is, everyone is likely to have gone through some degree of these symptoms while combating normal sadness. The current diagnostic guidelines conflates clinical depression with severe, but healthy sadness.</p><p>Mental Health advocates like such large projected patient figures because now it starts to look like this is a public health concern of massive proportions. This helps in reducing social stigma and diverting more resources to the problem. Pharmaceutical companies have obvious advantages from peddling drugs to healthy people with intense sorrow, misdiagnosed as mental health patients. And individuals may find comfort in the idea that the problems they face are because of an illness that would go away by taking some pills. The consequences of over and un-necessary medication is worrisome. The risks and side-effects of medication on healthy individuals has not been appropriately studied or assessed.</p><p>Even though some anti-depressant medications may help alleviate normal sadness, the misdiagnosis of personal sorrow as mental illness has damaging effects, particularly for younger people. Hardships is what trains our mind to form defence mechanisms and develop mental fortitude — it pushes one to identify and change the environmental factors that cause distress. Sadness is not something we need to run away from by popping pills. It is a healthy emotional response to something important going wrong in an individual’s life. And the natural come-back is to think hard, and systematically try to figure out how one might do something to change it. There is nothing wrong with wanting to feel better and if it involves taking medication, so be it. But it is unnecessary and dangerous to box up and label these natural emotions as mental disorder.</p><p>I cannot stress enough on the importance of being kind and sensitive to people combating severe sadness or clinical depression. Anything we do or say, is probably going to have a greater impact than we assume. It is irresponsible to belittle their problems. Having said that, trying to help a person who is suffering from natural, intense sadness, but has been misdiagnosed as a patient of MDD, is tricky. The internet is full of rubbish articles listing out things you should <strong><em>never</em></strong> say to a person struggling with depression (See for instance, <a href="http://www.lifehack.org/articles/communication/12-things-you-should-never-say-person-struggling-with-depression.html">http://www.lifehack.org/articles/communication/12-things-you-should-never-say-person-struggling-with-depression.html</a>). Going by these lists, there is virtually nothing you can say to a mis-labelled patient apart from platitudes like — “What can I do for you” and “I am here for you”. Any conversation regarding making changes or taking actions to help cope with the distress is considered insensitive. It seems impossible to have an honest conversation and bring a perspective differing from the so-called patient’s, to the table.</p><p>In conclusion, it is of utmost importance to have a more nuanced diagnosis of MDD, even at the cost of some inconsistencies. The DSM-4 in 1994 took a step in the right direction and included some minimum ‘clinically significant’ thresholds in diagnostic criteria. More academic discussions need to happen around reducing the rate of false positives in diagnosis of mental disorder. We must ensure that the clinically depressed patients and those suffering from severe sadness, get safe and effective treatment, most appropriate to their respective conditions.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9af42a917530" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Is India a ‘Hindu Country’?]]></title>
            <link>https://medium.com/@aiswaryamathur/is-india-a-hindu-country-ffac20a7beba?source=rss-f6b07002c404------2</link>
            <guid isPermaLink="false">https://medium.com/p/ffac20a7beba</guid>
            <category><![CDATA[atheism]]></category>
            <category><![CDATA[science]]></category>
            <category><![CDATA[religion]]></category>
            <category><![CDATA[hinduism]]></category>
            <category><![CDATA[india]]></category>
            <dc:creator><![CDATA[Aiswarya Prakasan]]></dc:creator>
            <pubDate>Fri, 24 Mar 2017 16:37:26 GMT</pubDate>
            <atom:updated>2017-03-25T05:40:00.166Z</atom:updated>
            <content:encoded><![CDATA[<p>I recently came across an article written by a German blogger, Maria Wirth, which is being circulated as a message on Whatsapp among Indians.</p><p>Here’s a gist of the article for those who want to skip <a href="https://mariawirthblog.wordpress.com/2013/05/04/when-germany-is-christian-is-india-hindu/">it</a> -</p><ul><li>Young and educated Indians do not want to associate India with ‘Hindutva’ or ‘Hinduism’ because they are buying into the Western propaganda that Western religions and culture are better than the ancient Sanatana Dharma (which is Hinduism today).</li><li>As an example, she contrasts India with Germany stating that inspite of the violent and tyrannical past of Christianity, Germany is still bracketed as a ‘Christian Country’ — major political parties encourage Christianity and Christian values etc.</li><li>The article is peppered with a lot of praise for Hinduism. She urges Indians to go back to their Hindu roots and embrace the Hindu values.</li></ul><p>Now, I could have just ignored this and moved on. But, I got the same message from 3 people and found this somewhat thought-provoking. To everyone whom I am going to offend with this article, I assure you I’m not being deliberately provocative. My intention is just to have a constructive discourse.</p><p>I am a strong proponent of secularism — separation of religion from government. And using terms like ‘Hindu Country’ irresponsibly, hits at the root of secular politics, sending the idea that the state is tied with Hinduism in some way. I understand the importance of strong morality in forming scalable public policies. However, the concept of religion as a moral compass is at best, weak and at worst, psychopathic. Weak — because we often have to metaphorize the supernatural hoo-ha to actually boil the ideas down to a practical form. And psychopathic because the gazillion years old scriptures often perpetuate horrible violence like stoning people to death or burning them alive. It just cannot act as a sufficiently good moral compass.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/1*GKwx1deiDbVmaSgsXVsWkQ.jpeg" /></figure><p>Some might argue that Hinduism is different from other religions and that it has a less bloody past. I agree that in its original form Sanatana Dharma (Hinduism) is not a rigid set of rules or a set of principles to be adhered to. It does not even talk about an omniscient, omnipotent creator or a personal God who answers to your prayers. I come from a Hindu family and everyone I know, believe in and practice Hinduism in its current form — with all the trappings of a classic, organised, dogmatic religion. Strip out all the belief in the supernatural about deities, personified Gods, spirits and netherworlds — and you won’t even identify the religion. I must also mention a new brand of spirituality being popularised by the likes of Deepak Chopra. This is the most dangerous because it sounds a lot like science. His strategy is to simply string together scientific jargon like ‘determinism’ and ‘quantum physics’ with religious words like ‘karma’ to whip out some senseless new-age gibberish. (See how a theoretical physicist reacts to his <a href="https://youtu.be/wi2IC6e5DUY?t=3839">constant misuse of the term quantum physics</a> as a justification to his incoherent magical claims.) Basically, every form of religion I know is fundamentally flawed.</p><p>Young and educated Indians not wanting to associate with Hinduism is not unusual. I don’t want to barrage you with statistics, but data makes it clear that more and more people are moving away from religion — a century ago in Canada, only 2% of the population claimed to have no religion, whereas today nearly 30% of Canadians claim as much, and approximately one in five does not believe in God. A century ago in Australia, less than 1% of the population claimed no religious identity, but today approximately 20% of Australians claim as much. The same trend is seen in Holland, Sweden, France, Japan and Israel. I could not get any data on India regarding this. But it seems obvious that the same trend must have followed here. Going back to what Maria says about Germany, I could not find a single credible reference to Germany as a ‘Christian country’. It definitely is a Christian-majority, secular country with steadily reducing religious adherence.</p><p>We should accept that culture is an ever-changing, complex, organic entity and can never be preserved in its pure form. It is only human to start questioning our belief system and what is ‘common sense’ in the light of new knowledge. If you tell me today that people could fly several centuries ago, there is no way I can buy that. When you have to pick and choose what to believe in and what not, it is just easier to abandon the whole school of thought.</p><p>In the article, Maria says about Hinduism — “<em>It is not a belief system that demands blind belief in dogmas and the suspension of one’s intelligence. On the contrary, Hinduism encourages using one’s intelligence to the hilt. The rishis enquired into truth, discovered universal laws and showed how to live life in an ideal way”</em>. Well, if you really are interested in the pursuit of truth based on intellectual honesty and humility, then there’s a better term for it — Science : the systematic study of nature through observation and experimentation. If this is what the <em>rishis </em>truly did and you want to follow them, follow the practice and don’t just unquestioningly accept something just because it has always been so. You cannot get new knowledge through prayers and intuition — it takes hard work.</p><p>I am not saying that religion has no place in the society. To many people, it gives hope and a mental model to deal with difficult times. Then there are traditions to celebrate important life events, festivals and a sense of belonging to a group. Most people would feel a void in their lives without the current socio-religious frameworks, even if they don’t believe all the supernatural nonsense. Hopefully, we will be able to establish some universal form of religion based on an intellectual culture of rationality and reasoning, and a moral culture of kindness, empathy and inclusion.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ffac20a7beba" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Project Euler #24 : Length of recurring cycle (repetend ) in decimal representation of a unit…]]></title>
            <link>https://medium.com/@aiswaryamathur/length-of-recurring-cycle-repetend-in-decimal-representation-of-a-unit-fraction-1afe6461cc59?source=rss-f6b07002c404------2</link>
            <guid isPermaLink="false">https://medium.com/p/1afe6461cc59</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[question-24]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[repetend-decimal]]></category>
            <category><![CDATA[project-euler]]></category>
            <dc:creator><![CDATA[Aiswarya Prakasan]]></dc:creator>
            <pubDate>Wed, 01 Mar 2017 02:51:27 GMT</pubDate>
            <atom:updated>2017-03-15T10:54:52.509Z</atom:updated>
            <content:encoded><![CDATA[<h3>Project Euler #24 : Length of recurring cycle (repetend ) in decimal representation of a unit fraction.</h3><p><strong>Problem</strong> — A unit fraction has 1 in the numerator. For eg — 1/2,1/3,1/4,1/5 etc. In their decimal representation they are —</p><p>1/2 = 0.5 <br>1/3 = 0.(3) <br>1/4 = 0.25 <br>1/5 = 0.2 <br>1/6 = 0.1(6) <br>1/7 = 0.(142857) <br>1/8 = 0.125 <br>1/9 = 0.(1) <br>1/10 = 0.1</p><p>Where 0.1(6)means , 0.1666666… and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle. Given an integer N, find the smallest value of d&lt;N, such that d has the longest recurring cycle.</p><p>For eg, if N=10, the output should be 7 (1/7 has the longest recurring cycle).</p><p>This is problem <a href="https://projecteuler.net/problem=26">26</a> from <a href="https://projecteuler.net/">Project Euler</a>. Another variation is at <a href="https://www.hackerrank.com/contests/projecteuler/challenges/euler026">hackerrank</a> (different input size).</p><p><strong>The Math- </strong>One way of solving this problem is using Brute Force (long division method). That might be enough to solve the Project Euler problem. However, with bigger input of the hackerrank problem, this approach will not work. Here is a cleverer solution.</p><p>If we write down the first few unit fractions in decimal form, we can identify three different types of fractions –</p><ol><li><strong><em>Terminating Fractions</em></strong> — These are the fractions that do not have a repeating cycle. For eg, 1/2 = 0.5 , 1/4 = 0.25 , 1/5 = 0.2 etc.</li><li><strong><em>Completely Repeating</em></strong> — The fractions like 1/3 = 1.(3), 1/7 = 1.(142857), 1/9 = 1.(1) etc where the entire decimal part is repeating.</li><li><strong><em>Repeating after a non-repeating part — </em></strong>An example is 1/6, where repetition starts in the decimal part after a few non-repeating digits. <br>1/6 = .1(6) where ‘1’ is non-repeating.</li></ol><p><strong>Case 1 : Terminating Fractions</strong></p><p>The terminating fractions are not of interest to us in this question as the length of repeating cycle in these will always be equal to 0. However, we need to identify the integers whose reciprocals form terminating fractions. If 1/n is a terminating decimal, there exists an integer<em> k</em>, such that-</p><pre>10^k*(1/n) -&gt; is an integer</pre><p>For eg,<br>10²(1/4) = 100*0.25 = 25 =&gt; Here, k = 2.<br>10¹(1/5) = 10*0.2 = 2 =&gt; Here, k = 1.</p><p>This implies</p><pre>=&gt; 10^k mod n = 0<br>          =&gt; n is a factor of 10^k.</pre><p>This is only possible if</p><pre>n = (2^a*5^b) ; for some a and b</pre><p>And k will be equal to the greater of ‘<em>a’</em> and ‘<em>b’.<br></em>For eg,<br><em> </em>1/4 = 1/2²<br><em> </em>10²/2²<em> = 25<br></em>Here, k = 2.</p><pre>If a number can be represented as (2^a)*(5^b), its reciprocal is a <br>terminating decimal.</pre><p><strong>Case 2: Completely Repeating decimal</strong></p><p>If 1/n is a completely repeating decimal, there exists an integer <em>k</em> such that –</p><pre>10^k*(1/n) has the same decimal part as (1/n)</pre><p>For eg,<br>1/7 = 0.(142857) ……………………………………… (eqn 1)<br>10⁶(1/7) = 142857.(142857) ……………………………….(eqn 2)<br>Here, k = 6.<br>This implies –</p><pre>                10^k*(1/n)-(1/n) -&gt; is an integer<br>             =&gt; (10^k -1)/n -&gt; is an integer<br>             =&gt; (10^k-1) mod n = 0<br>             =&gt; 10^k mod n = 1 ......................(eqn 3)</pre><p>For eg,<br>Subtracting (eqn 1) from (eqn 2), we have:<br>10⁶(1/7)-(1/7) = 142857<br>Here, 10⁶ mod 7 = 1</p><pre>For a given <em>n</em>, if we find the least value of <em>k</em>, for which (eqn 3) <br>holds true, the length of the repeating decimal cycle for the <br>reciprocal of <em>n</em> is <em>k</em>.</pre><p><strong>Case 3: Repeating after a non-repeating part</strong></p><p>Thinking on the same lines as Case 1 and Case 2, we need to look for a way to represent a decimal that repeats after a non-repeating part as an integer. An example is 1/6 = .1(6).<br>Here, non-repeating part is of length 1 and repeating part is also of length 1.</p><p>We can multiply 1/n by a certain power, d, of 10 such that the non-repeating decimal part is on the left side of the decimal point.<br>If 1/n is a decimal value that repeats after a non-repeating part, there exists an integer <em>d </em>such that-</p><pre>        10^d*(1/n) -&gt; a completely repeating decimal.</pre><p>For eg,<br>1/6 = 0.1(6)<br>=&gt; 10¹*(1/6) = 1.(6) …………………………………………………(eqn 1)<br>Here, d = 1</p><p>There also exists an integer <em>k </em>such that</p><pre>      (10^(d+k))(1/n) has the same decimal part as 10^d(1/n)</pre><p>For eg,<br>=&gt; 10^(1+1)*(1/6) = 10²(1/6) = 16.(6)……………………………..(eqn 2)<br>Here, k = 1</p><p>This implies-</p><pre>          10^(d+k)(1/n)-10^d(1/n) -&gt; is an integer<br>       =&gt; (10^(d+k) -10^d)/n -&gt; is an integer<br>       =&gt; 10^d(10^k-1)/n = 0<br>       10^d cancels out with all 2&#39;s and 5&#39;s from n.<br>       If n = (2^a)*(5^b)*other factors, for some a and b.  <br>       n&#39; = n/(2^a)(5^b) [Removing all 2s and 5s]<br>       d = max(a,b) such that 10^d cancels out all multiples of 2 and 5 from n.<br>       Now, we can solve this independently as-<br>       (10^k-1)/n&#39; -&gt; is an integer.<br>       From Case2, this implies that we solve for-<br>       10^k mod n&#39; = 1 .....................................(eqn 3)</pre><p>For eg,<br>Subtracting (eqn1) from (eqn2), we have-<br>10²(1/6) — 10(1/6) = 15<br>=&gt; 10(10–1)/6 = 15<br>=&gt; 5(10–1)/3 = 15 ( Cancelling out multiples of 2 and 5 from n)<br>Now, we solve the part (10–1)/3 independently<br>From Case2, this implies that we solve for =&gt; 10^k mod 3 = 1. Here, k=1.</p><p>Once all multiples of 2 and 5 are cancelled out from n, it can be solved as Case 2 from above. In other words, the non-repeating part of the decimal representation is contributed to by the 2’s and 5’s in n. Since we are interested in the repeating cycle, we can factorize n, remove all multiples of ( 2 and 5) and solve it as for Case 2 above.</p><pre>For a given n, if we first find <em>n&#39; = n/(2^a*5^b)</em> {for maximum a and b}, and find the least value of <em>k</em>, for which (eqn 3) holds true, the<br>length of the repeating decimal cycle for the reciprocal of <em>n</em> is <em>k</em>.</pre><p><strong>Overview of the Algorithm</strong>–</p><ol><li>For every integer n less than the input bound in question, represent it as a co-prime number of 10, ie. remove all 2’s and 5’s to represent it in the form <em>n’= n/(2^a*5^b)</em> {for max a and b}.</li><li>Find the longest repeating decimal cycle by solving the following eqn for k — <strong><em>n’^k mod n’=1</em></strong></li><li>Save the value of n for which we have found the longest cycle so far. This can be used as a lookup for queries in <a href="https://www.hackerrank.com/contests/projecteuler/challenges/euler026">Hackerrank question</a>.</li></ol><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bed950a6edc727da4d6f2b1d49cb0aa5/href">https://medium.com/media/bed950a6edc727da4d6f2b1d49cb0aa5/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1afe6461cc59" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding Fast Fourier Transform from scratch — to solve Polynomial Multiplication.]]></title>
            <link>https://medium.com/@aiswaryamathur/understanding-fast-fourier-transform-from-scratch-to-solve-polynomial-multiplication-8018d511162f?source=rss-f6b07002c404------2</link>
            <guid isPermaLink="false">https://medium.com/p/8018d511162f</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[polynomial-multiplication]]></category>
            <category><![CDATA[fast-fourier-transform]]></category>
            <dc:creator><![CDATA[Aiswarya Prakasan]]></dc:creator>
            <pubDate>Thu, 23 Feb 2017 17:30:09 GMT</pubDate>
            <atom:updated>2017-02-23T17:30:09.317Z</atom:updated>
            <content:encoded><![CDATA[<p>Fast Fourier Transform is a widely used algorithm in Computer Science. It is also generally regarded as difficult to understand. I have spent the last few days trying to understand the algorithm — how it works and why. In the process I digressed to various other mathematical topics to build a complete understanding ground up. Here, I have tried to collate and document everything I have learnt. In this blog, we will use FFT (Fast Fourier Transform) to solve the problem of quickly multiplying two polynomials. I must warn that this is a long (and tedious?) post. But, you should be able to read and understand everything from start to end without having to look anything up.</p><p><strong>Prerequisites</strong> — <strong><em>You do not need to know Fourier Transform to understand this blog</em></strong>. However, a basic understanding of the following is required -</p><ul><li>Polynomials</li><li>Complex Numbers</li><li>Trigonometry</li><li>Matrix Multiplication</li><li>Algorithm Complexity Analysis (Big O notation) — You are free to skip these parts and it shouldn’t affect the understanding of working of the algorithm.</li></ul><p><strong>Problem</strong> — Given two polynomials- A(x) =a0+a1x+a2x^2+… anx^n and B(x) =b0+b1x+b2x^2+… bnx^n, find the polynomial C(x) = A(x)*B(x).</p><pre>E.g., multiply (x^2 + 2x + 3)(2x^2 + 5) = <br><br>			2x^2 + 0x + 5<br>			1x^2 + 2x + 3<br>                        -------------<br>                        6      0   15<br>                 4      0      10<br>      2     0      5<br>         ----------------------------<br>          2x^4 + 4x^3 + 11x^2 +10x+15</pre><p>More generally, when C(x) = A(x)*B(x) and C(x) =c0+c1x+c2x^2+... c2nx^2n .</p><pre>ci = a0*bi + a1*bi-1 + ... + ai*b0.</pre><p>If we think of A and B as vectors, then C vector is called &#39;<strong><em>Convolution</em></strong>&#39; of A and B (<em>represented as </em><strong><em>{A⊗B}</em></strong>). Make sure that the polynomials A and B are appropriately appended with 0s to make each of their degree equal to 2n (degree of C). Straightforward computation is <strong><em>O(n^2)</em></strong> time</p><p><strong>Fourier Transform and Convolution Theorm</strong></p><p>Fourier analysis is the decomposition of any mathematical function into a series of sine and cosine waves (sinusoids). If you wish to learn more, here are some links that help build the intuition — <a href="https://www.quora.com/What-is-an-intuitive-explanation-of-the-FFT-algorithm">a quora answer on fft</a>, <a href="https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/">an interactive guide to Fourier Transform</a>.</p><p>We generally represent a function in its Fourier Transform form, as it is easier to work with.</p><p><strong><em>The Convolution Theorm</em> : </strong>states that under suitable conditions the Fourier transform of a convolution (denoted by ‘⊗’) is the point-wise product of Fourier transforms. Let <strong><em>f</em></strong> and <strong><em>g </em></strong>be two functions with convolution <strong><em>{f⊗ g}. </em></strong>Fourier transform be denoted by the operator ‘<strong>ζ’ </strong>so <strong><em>ζ(f)</em></strong> and <strong><em>ζ(g)</em></strong> are the Fourier transforms of <strong><em>f</em> </strong>and <strong><em>g</em></strong>, respectively. -</p><pre><strong><em>ζ(f⊗g) = ζ(f).ζ(g)</em></strong></pre><p>The convolution operation is converted to point-wise multiplication (we will discuss what point-wise multiplication means).</p><p><strong>Representation of Polynomials</strong></p><p>The representation of Polynomial we saw above is called the <strong><em>coefficient representation</em></strong><em>. </em>Another way of representing a polynomial is called <strong><em>point-value representation</em></strong>. A polynomial of degree n-1 can be uniquely represented by its values at at-least n different points. This is a result of the <strong><em>Fundamental Theorm of Algebra</em></strong> that states — <strong><em>“A degree n-1 polynomial A(x) is uniquely specified by its evaluation at n distinct values of x”</em></strong>.</p><p>A polynomial A(x) =a0+a1x+a2x^2+… anx^n can be represented as</p><pre>A set of n pairs {(x0, y0),(x1, y1),...,(xn, yn)} such that <br>• for all i != j, xi != xj. ie, the points are unique. <br>• for every k, yk = A(xk);</pre><p>In point-value form, multiplication 𝐶(𝑥) = 𝐴(𝑥)𝐵(𝑥) is given by 𝐶(𝑥𝑘) = 𝐴(𝑥𝑘) .𝐵(𝑥𝑘) for any point (𝑥𝑘).</p><pre>If 𝐴 and 𝐵 are of degree-bound &#39;<em>n&#39;</em>, then 𝐶 is of degree-bound &#39;<em>2n&#39;</em>.<br>Need to start with “extended” point-value forms for 𝐴 and 𝐵 consisting of <br>2𝑛 point-value pairs each. – <br><br>𝐴: (𝑥0, 𝑦0) , (𝑥1, 𝑦1) , … ,( 𝑥2𝑛−1, 𝑦2𝑛−1) <br>𝐵: (𝑥0, 𝑦0&#39;)  , (𝑥1, 𝑦1 ′) , … , (𝑥2𝑛−1, 𝑦2𝑛−1 ′) <br>𝐶: (𝑥0, 𝑦0𝑦0 ′) ,( 𝑥1, 𝑦1𝑦1 ′) , … ,( 𝑥2𝑛−1, 𝑦2𝑛−1𝑦2𝑛−1 ′)</pre><p>For example,<br>𝐴(𝑥) = 𝑥 ^3 − 2𝑥 + 1<br>𝐵 𝑥 = 𝑥 ^3 + 𝑥^ 2 + 1<br>𝑥𝑘 = (−3, −2, −1, 0, 1, 2, 3) We need 7 coefficients!<br>𝐴: (−3,−17) ,( −2,−3) ,( −1,1) ,( 0, 1) ,( 1, 0) , (2, 5) , (3, 22)<br>𝐵: (−3,−20) ,(−2,−3) , (−1, 2) ,( 0, 1) ,( 1, 3) ,( 2, 13) ,( 3, 37)<br>𝐶: (−3,340) , (−2,9) , (−1,2) ,( 0, 1) ,( 1, 0) ,( 2, 65) ,( 3, 814)</p><p>This is point-wise multiplication. The time to multiply two polynomials of degree-bound <em>n</em> in point-value form is <strong><em>Θ(n)</em></strong>.The inverse of evaluation--determining the coefficient form of a polynomial from a point-value representation--is called <strong><em>interpolation.</em></strong> This is what the Convolution Theorm states with respect to Fourier Transform of a function.</p><p><strong>The Road so far</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/894/0*cQ0jrt_xq810yIJK.png" /></figure><p>Now the efficiency of our algorithm depends on the efficiency of conversion between the two representation -</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/732/0*YV7i5Bh-GEN_awWn.png" /></figure><p>This is where we use the FFT algorithm.</p><p><strong>An Overview of the Algorithm</strong></p><pre>Let m = 2n-1. [so degree of C is less than m]<br>1. Pick m points x_0, x_1, ..., x_{m-1} chosen <em>cleverly</em>.<br>2. Evaluate A at each of the points: A(x_0),..., A(x_{m-1}).<br>3. Same for B.<br>4. Now compute C(x_0),..., C(x_{m-1}), where C is A(x)*B(x)<br>5. Interpolate to get the coefficients of C.</pre><p>At a glance, it looks like points 2 and 3 from the Algorithm takes O(n^2) time. However, the FFT will allow us to quickly move from <strong><em>coefficient representation</em></strong> of polynomial to the <strong><em>point-value representation</em></strong>, and back, for our cleverly chosen set of m points. (Doesn’t work for arbitrary m points. The special points will turn out to be the roots of unity).</p><p><strong>A Detour to Roots of Unity</strong></p><p>The word “root” in the term refers to square roots, cube roots, and any other roots you might happen to need. For any integer <em>n</em>, the <em>n</em>th root of a number <em>k</em> is a number that, when multiplied by itself <em>n</em> times, yields <em>k</em>. The word “unity,” means “one.” So a root of unity is any number which, when multiplied by itself some number of times, yields 1. To get any root of unity, other than 1, we need to delve into Complex Numbers.</p><p>We can think of the set of complex numbers as a 2-dimensional plane. We specify a complex number with two coordinates the same way we would on a graph: the point (1,1) refers to the number 1+i. If we were standing on the point (0,0), we probably wouldn’t want to walk one unit over and then one unit up to get to the point (1,1). Instead, we’d take a diagonal by walking √2 units at an angle of 45 degrees to the x-axis. Notationally, when we use this radial distance and direction, we write a complex number as <em>re^i θ</em>, where <em>r</em> is the distance and θ is the direction, usually written in radians rather than degrees. There are 2π radians in a whole circle, so the number 1 is written e^i 2π. The angle 45 degrees is π/4 radians, so the point (1,1) that we found above would be written as √2e^i π/4.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*7RnJiRjuLQlBxonD.png" /></figure><p>This method of specifying a point with a length and a direction is called using polar coordinates.<br>If a point is represented as re^iθ, the x-co-ordinate(real part) is given by rcosθ, and the y-co-ordinate (imaginary part) is given by rsinθ. This follows from basic trigonometric identities.</p><pre>  polar coordinates : re^iθ<br>  cartesian coordinates :(rcosθ, rsinθ)</pre><p>Multiplication with the polar notation of <em>re^iθ</em>, is really easy: <br>you multiply the distances together and add the angles. So 5e^iπ/6× 2e^iπ/3=10e^i π/2. So multiplying involves both expansion or contraction (that’s the distance part) and rotation (that’s the angle part).</p><p>If we have a number written <em>re^i θ</em> which, when multiplied by itself a certain number of times, yields 1, the distance <em>r</em> itself must be 1. If <em>r</em> were larger than 1, say 2, then as we multiplied the number by itself more and more times, its distance from (0,0) would go from 2 to 4 to 8 and on and on, spiralling out to infinity. If <em>r</em> were smaller than 1, say 1/2, the point would spiral in to 0: 1/2, 1/4, 1/8, and so on. 1 is the only radial distance that will stay perfectly balanced, just moving around the circle as we multiply the numbers together.</p><p>To make this more concrete, I happen to know that e^i2π/7 is a root of unity. When I raise it to the 7th power, I get e^i2π, which is 1. Each time I multiply e^i2π/7 by itself (product =e^i(2*2π/7)) , I rotate 1/7 of the way around the circle. In fact, as I multiply e^i2π/7 by itself successively, I get this picture -</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/796/0*1SM0YAm6epxImWe_.png" /></figure><p>In fact, there are seven 7th roots of unity, and each gold disc in that picture is one of them. We can get an <em>n</em>th root of unity for any number <em>n</em> by replacing the 7 in e^i2π/7 by <em>n. </em>The pictures for other roots of unity look a lot like that diagram above, they just have a different number of gold discs.</p><p>There are exactly n complex nth root of unity e^2𝜋𝑖𝑘/𝑛 for k = 0, 1, … , <br>𝑛 − 1 where <strong><em>e^iu= cos (u) + 𝑖 sin(u)</em></strong>. Here <em>‘u’</em> represents an angle in radians.</p><p><strong><em>Visualising 8th roots of unity-</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/816/0*9LFiRIrkh4n6XPLA.png" /></figure><p><strong>Some Interesting Properties of Roots of Unity</strong></p><ol><li><strong><em>Principal nth Root of Unity</em></strong></li></ol><ul><li>The value <em>ω𝑛</em> = e^2𝜋𝑖/𝑛 is called the principal nth root of unity.</li><li>All of the other complex nth roots of unity are powers of 𝜔𝑛.</li><li>The n complex nth roots of unity, 𝜔𝑛^0 , 𝜔𝑛^1 , … ,𝜔𝑛^n-1 form a group under multiplication that has the same structure as (ℤn, +) modulo n.</li><li>𝜔𝑛^𝑛 = 𝜔𝑛^0 = 1 implies<br>– 𝜔𝑛^𝑗.𝜔𝑛^𝑘 = 𝜔𝑛^(𝑗+𝑘) = 𝜔𝑛^((𝑗+𝑘) mod n)<br>– <em>𝜔𝑛^-1 = 𝜔𝑛^n-1</em></li></ul><p><strong><em>2. Cancellation Lemma</em></strong></p><ul><li>For any integers <em>n</em> ≥ 0, <em>k</em> ≥ 0, and <em>b</em> &gt; 0, 𝜔𝑑𝑛^𝑑𝑘 = 𝜔𝑛^𝑘.</li><li>Proof : 𝜔𝑑𝑛^𝑑𝑘 = (𝑒^(2𝜋𝑖/dn))^dk = 𝑒^(2𝜋𝑖/nk) = 𝜔𝑛^𝑘</li><li>For any even integer <em>n</em> &gt; 0, 𝜔𝑛^(𝑛/2) = 𝜔2 = −1.</li><li>Example 𝜔24^6 = 𝜔4<br>– 𝜔24^6 = (𝑒^(2𝜋𝑖/24))6 = 𝑒^(2𝜋𝑖*6/24) = 𝑒^2𝜋𝑖/4 = 𝜔4</li></ul><p><strong><em>3. Halving Lemma</em></strong></p><ul><li>If <em>n</em> &gt; 0 is even, then the squares of the <em>n </em>complex <em>n-</em>th roots of unity are the <em>n/2</em> complex <em>n/2-</em>th roots of unity.</li><li>Proof : By the cancellation lemma, we have( 𝜔𝑛 ^𝑘) 2 = 𝜔𝑛/2^ 𝑘 for any non-negative integer, 𝑘.</li><li>If we square all of the complex <em>n-</em>th roots of unity, then each <em>n/2^</em>th root of unity is obtained exactly twice .<br>– (𝜔𝑛^(𝑘+𝑛/ 2))2 = 𝜔𝑛^(2𝑘+𝑛) = 𝜔𝑛^2𝑘*𝜔𝑛^𝑛 = 𝜔𝑛^2𝑘 = (𝜔𝑛^<em>k</em>)^2<br>–Thus, 𝜔𝑛^𝑘 and 𝜔𝑛^(𝑘+𝑛/2) have the same square.</li></ul><pre>As we will see, the fast Fourier transform algorithm cleverly makes <br>use of the following properties about <em>ωn</em>:<br>   <em>𝜔𝑛^n =1<br>   𝜔𝑛^n+𝑘 = 𝜔𝑛^𝑘<br>   𝜔𝑛^n/2 = -1<br>   𝜔𝑛^(n/2+𝑘) = -𝜔𝑛^</em>𝑘</pre><p><strong>Discrete Fourier Transform</strong></p><p>Since we have broken up the problem, our goal now is to evaluate a given polynomial, A (x)(degree &lt;m) at m points of our choosing in total time O(m log m). Assume m is a power of 2.</p><p>Let’s first develop it through an example.</p><p>Say m=8, so we have a polynomial<br>A(x) = a_0 + a_1 x + a_2 x² + a_3 x³ + a_4 x⁴ + a_5 x⁵ + a_6x⁶ + a_7x⁷.<br>(as a vector, A = [a_0, a_1, …, a_7])</p><p>And we want to evaluate at eight points of our choosing. Here is an idea. Split A into two pieces, but instead of left and right, have them be even and odd. So, as vectors,<br>A_even = [a_0, a_2, a_4, a_6]<br>A_odd = [a_1, a_3, a_5, a_7]</p><p>or, as polynomials:</p><p>A_even(x) = a_0 + a_2 x + a_4 x² + a_6 x³<br>A_odd(x) = a_1 + a_3 x + a_5 x² + a_7 x³.</p><p>Each has degree &lt; m/2. How can we write A(x) in terms of A_even and A_odd?<br>A(x) = A_even(x²) + x A_odd(x²).<br>A(-x) = A_even(x²) — x A_odd(x²).</p><p>Now, instead of calculating the value for 1 polynomial of degree m, we now need to calculate 2 polynomials of degree (m/2) and then combine them.</p><p>Let T(m) = time to evaluate a degree-m polynomial at our special set of m points. We’re doing this by evaluating two degree-m/2 polynomials at m/2 points each (the squares), and then doing O(m) work to combine the results. This is great because the recurrence T(m) = 2T(m/2) + O(m) solves to O(m log m).</p><p>What’s nice is that the effort spent computing A(x) will give us A(-x) almost for free. So, we need to specially choose m points that will have the property:</p><pre>The 2nd half of points are the negative of the 1st half   (***)</pre><p>E.g., {1,2,3,4,-1,-2,-3,-4}.</p><p>But, we’re deluding ourselves by saying “just do it recursively”. Why is that? The problem is that recursively, our special points (now {1, 4, 9, 16}) have to satisfy property (***). E.g., they should really look like {1, 4, -1, -4}. But these are squares! To fix these we use complex numbers. E.g., if these are the squares, what do the original points look like?</p><p>{1, 2, i, 2i, -1, -2, -i, -2i}</p><p>so then their squares are: 1, 4, -1, -4<br>and their squares are: 1, 16</p><p>But, at the next level we again need property (***). So, we want to have {1, -1} there. This means we want the level before that to be {1, i, -1, -i}, which is the same as {1, i, i^2, i^3}.</p><p>So, for the original level, let ω = the primitive 8th root of unity, and then our original set of points will be:</p><p>1,ω ,ω^2,ω^3,ω^4 (= -1),ω^5 (= -ω ),ω^6 (= -ω^2),ω^7 (= -ω^3)</p><p>so that the squares are: 1, i, i² (= -1), i³ (= -i)<br>and *their* squares are: 1, -1<br>and *their* squares are: 1</p><p>In general, the mth primitive root of unity is the vector<br>ω = cos(2*pi/m) + i*sin(2*pi/m)</p><pre><strong>Fast Fourier Transform (FFT)</strong> </pre><pre>The problem of evaluating 𝐴(𝑥) at 𝜔𝑛^0 , 𝜔𝑛^1 , … , 𝜔𝑛^𝑛−1 reduces to <br>   1. evaluating the degree-bound 𝑛/2 polynomials 𝐴even(𝑥) and 𝐴odd(𝑥) at the points (𝜔𝑛^0)^2 ,(𝜔𝑛^1)^2 , … , (𝜔𝑛^𝑛−1)^2. <br>   2. combining the results by 𝐴(𝑥) = 𝐴even(𝑥2) + 𝑥𝐴odd(𝑥2). </pre><pre><br>Why bother? </pre><pre>– The list (𝜔𝑛^0)^2 ,(𝜔𝑛^1)^2 , … , (𝜔𝑛^𝑛−1)^2 does not contain <br>𝑛 distinct values, but 𝑛/2 complex 𝑛/2-th roots of unity. <br>– Polynomials 𝐴even and 𝐴odd are recursively evaluated at the 𝑛/2                                        complex 𝑛/2-th roots of unity. <br>– Subproblems have exactly the same form as the original problem, but are half the size</pre><p><strong>Example</strong><br>A(x) = 3+2x+3x^2+4x^3<br>A(<em>ω4^0) = A(1) = 3+2+3+4=12<br>A(ω4^1) = A(i) = 3+2i-3+4i=6i<br>A(ω4^2) = A(-1) = 3–2+3–4=0<br>A(ω4^3) = A(-i) = 3–2i-3+4i=2i</em></p><p>Using A(x)= Aeven(x^2) + xAodd(x^2)<br>Aeven(x) = 3+3x<br>Aodd(x) = 2+4x<br>A(<em>ω4^0</em>)= A(1) = Aeven(1)+1.Aodd(1)= 3+3+2+4=12<br>A(<em>ω4^1</em>)= A(i) = Aeven(-1)+i.Aodd(-1)=<em>3–3+2i+4i=6i<br>A(ω4^2)= A(-1) = Aeven(1)-1.Aodd(1)= 3+3–2–4=0<br>A(ω4^3)= A(-i)= Aeven(-1)-i.Aodd(-1)=3–3–2i+4i= 2i</em></p><pre><strong>Algorithm</strong><br>Here is the general algorithm in pseudo-C:<br><br>Let A be array of length m, w be primitive mth root of unity.<br>Goal: produce DFT F(A): evaluation of A at 1, w, w^2,...,w^{m-1}.<br>FFT(A, m, w)<br>{<br>  if (m==1) return vector (a_0)<br>  else {<br>    A_even = (a_0, a_2, ..., a_{m-2})<br>    A_odd  = (a_1, a_3, ..., a_{m-1})<br>    F_even = FFT(A_even, m/2, w^2)//w^2 is a m/2-th root of unity<br>    F_odd = FFT(A_odd, m/2, w^2)<br>    F = new vector of length m<br>    x = 1<br>    for (j=0; j &lt; m/2; ++j) {<br>      F[j] = F_even[j] + x*F_odd[j]<br>      F[j+m/2] = F_even[j] - x*F_odd[j]<br>      x = x * w<br>  }<br>  return F<br>}</pre><p>Note : To apply this algorithm, ‘<em>m’</em> should be a power of 2.We should pad<br>extra zeros to the polynomial to ensure that length of the array is a<br>power of 2. This algorithm returns an array of complex numbers which is<br>then used for point-wise multiplication.</p><p><em>Here is the tree of input vectors to the recursive calls of the FFT procedure. The initial invocation is for n = 8.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/882/0*bzttGpowYy_C41cV.png" /></figure><p><strong>Inverse Fourier Transform</strong></p><p>Once we perform point-wise multiplication on the Fourier Transforms of A and B and get C (an array of Complex Numbers), we need to convert it back to coefficient form to get the final answer.</p><p>We use the Inverse Fourier Transform to get the coefficient form of C (Don’t worry about the imaginary part of the complex number. Once the Inverse Fourier Transform is performed, we get an array of Complex Numbers with the imaginary part almost equal to 0. Hence ,it can be ignored.</p><p>What we have actually done so far (computing A(x) at 1, ω,ω2, …,ω{m-1}) can be represented as-</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/504/0*M7XzJH7-f2DpaDlU.png" /></figure><p>This can be represented in the matrix form as -</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/830/1*x09PwtSACRRXcylIKegnRA.png" /></figure><p>Lets use F to denote the matrix of primitive roots. In order to retrieve the coefficients, we need to get F^-1(inverse of matrix F) , and multiply it with the y- matrix. It turns out that F^-1 looks the same. In place of ω, the inverse Fourier Matrix uses ω^-1.</p><pre>if <em>ω</em> = a+ib   =&gt; <em>ω^-1</em> = a-ib<br>if <em>ω</em> = e^2Πi/k  =&gt; <em>ω^-1</em> = e^-2Πi/k</pre><p>so, F^-1</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/616/0*dJZMGnzH3x7dBcbe.png" /></figure><p>Based on the above observation, we can still apply FFT by replacing a with y, y with a, ωn with ωn^−1 (that is, ωn^n-1 ), and scaling the result by 1/n .</p><pre>So, the final algorithm is:<br><br>    Let F_A = FFT(A, m, ω)                        // time O(n log n)<br>    Let F_B = FFT(B, m, ω)                        // time O(n log n)<br>    For i=1 to m, let F_C[i] = F_A[i]*F_B[i]      // time O(n)<br>    Output C = 1/m * FFT(F_C, m, ω-1). // time O(n log n)</pre><p>I will be adding the full Java code for polynomial multiplication in a couple of hours.</p><p><em>References : </em><br><em> </em><a href="http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/lectures/lect0423.txt"><em>http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/lectures/lect0423.txt</em></a><br><em> </em><a href="https://www.cs.princeton.edu/~wayne/teaching/fft.pdf"><em>https://www.cs.princeton.edu/~wayne/teaching/fft.pdf</em></a><br><em> </em><a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/lecture-notes/MIT6_046JS12_lec05.pdf"><em>https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/lecture-notes/MIT6_046JS12_lec05.pdf</em></a><br><em> </em><a href="http://web.cs.iastate.edu/~cs577/handouts/polymultiply.pdf"><em>http://web.cs.iastate.edu/~cs577/handouts/polymultiply.pdf</em></a><br><em> </em><a href="http://web.cecs.pdx.edu/~maier/cs584/Lectures/lect07b-11-MG.pdf"><em>http://web.cecs.pdx.edu/~maier/cs584/Lectures/lect07b-11-MG.pdf</em></a><br><em> </em><a href="https://blogs.scientificamerican.com/roots-of-unity/what-are-roots-of-unity/"><em>https://blogs.scientificamerican.com/roots-of-unity/what-are-roots-of-unity/</em></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8018d511162f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Find the N-th permutation of an ordered string (Using factorial number system).]]></title>
            <link>https://medium.com/@aiswaryamathur/find-the-n-th-permutation-of-an-ordered-string-using-factorial-number-system-9c81e34ab0c8?source=rss-f6b07002c404------2</link>
            <guid isPermaLink="false">https://medium.com/p/9c81e34ab0c8</guid>
            <category><![CDATA[factorial-number-system]]></category>
            <category><![CDATA[project-euler]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[lemer-code]]></category>
            <dc:creator><![CDATA[Aiswarya Prakasan]]></dc:creator>
            <pubDate>Sun, 19 Feb 2017 16:22:46 GMT</pubDate>
            <atom:updated>2017-02-19T16:25:01.076Z</atom:updated>
            <content:encoded><![CDATA[<p>Problem — If all of the permutations of a string are listed alphabetically, we call it lexicographic order. What is the nth lexicographical permutation of a given string?</p><p>Instead of finding all permutations and looking up the nth, we can directly calculate the nth permutation. We need to first understand the Factorial Number System (or Factoradic number system) to solve this question. A factorial number system uses factorial values instead of powers of numbers (binary system uses powers of 2, decimal uses powers of 10) to denote place-values (or base).</p><p>The place values (base) are -</p><pre>5!= 120    4!= 24    3!=6    2!= 2    1!=1    0!=1 etc..</pre><p>The digit in the zeroth place is always 0. The digit in the first place (with base = 1!) can be 0 or 1. The digit in the second place (with base 2!) can be 0,1 or 2 and so on. Generally speaking, the digit at nth place can take any value between 0-n.</p><p>First few numbers represented as factoradics-</p><p>0 -&gt; 0 = 0*0!<br>1 -&gt; 10 = 1*1! + 0*0!<br>2 -&gt; 100 = 1*2! + 0*1! + 0*0!<br>3 -&gt; 110 = 1*2! + 1*1! + 0*0!<br>4 -&gt; 200 = 2*2! + 0*1! + 0*0!<br>5 -&gt; 210 = 2*2! + 1*1! + 0*0!<br>6 -&gt; 1000 = 1*3! + 0*2! + 0*1! + 0*0!<br>7 -&gt; 1010 = 1*3! + 0*2! + 1*1! + 0*0!<br>8 -&gt; 1100 = 1*3! + 1*2! + 0*1! + 0*0!<br>9 -&gt; 1110<br>10-&gt; 1200</p><p>There is a direct relationship between nth lexicographical permutation of a string and its factoradic representation.</p><p>For example, here are the permutations of the string “abcd”.</p><pre>0  abcd       6  bacd        12  cabd       18  dabc<br>1  abdc       7  badc        13  cadb       19  dacb<br>2  acbd       8  bcad        14  cbad       20  dbac<br>3  acdb       9  bcda        15  cbda       21  dbca<br>4  adbc       10  bdac       16  cdab       22  dcab<br>5  adcb       11  bdca       17  cdba       23  dcba</pre><p>We can see a pattern here, if observed carefully. The first letter changes after every 6th (3!) permutation. The second letter changes after 2(2!) permutation. The third letter changed after every (1!) permutation and the fourth letter changes after every (0!) permutation. We can use this relation to directly find the nth permutation.</p><p>Once we represent <em>n</em> in factoradic representation, we consider each digit in it and add a character from the given string to the output. If we need to find the 14th permutation of ‘abcd’. 14 in factoradics -&gt; 2100.</p><p>Start with the first digit -&gt;2, String is ‘abcd’. Assuming the index starts at 0, take the element at position 2, from the string and add it to the Output.</p><pre>Output               String<br>  c                   abd<br>  2                   012</pre><p>The next digit -&gt; 1.String is now ‘abd’. Again, pluck the character at position 1 and add it to the Output.</p><pre>Output               String<br> cb                    ad<br> 21                    01</pre><p>Next digit -&gt; 0. String is ‘ad’. Add the character at position 1 to the Output.</p><pre>Output               String<br> cba                    d<br> 210                    0</pre><p>Next digit -&gt; 0. String is ‘d’. Add the character at position 0 to the Output.</p><pre>Output              String<br> cbad                 &#39;&#39;<br> 2100</pre><p>To convert a given number to Factorial Number System,successively divide the number by 1,2,3,4,5 and so on until the quotient becomes zero. The reminders at each step forms the factoradic representation.</p><p>For eg, to convert 349 to factoradic,</p><pre>Quotient        Reminder        Factorial Representation<br>349/1            349               0                             0<br>349/2            174               1                            10<br>174/3            58                0                           010<br>58/4             14                2                          2010<br>14/5             2                 4                         42010<br>2/6              0                 2                        242010</pre><p>Factoradic representation of 349 is 242010.</p><p>Java Code -</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/dc28cf5220fe9683c1587c2c85e4ee30/href">https://medium.com/media/dc28cf5220fe9683c1587c2c85e4ee30/href</a></iframe><p>Driver code to test the functions in Java -</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fc197c7df8438d87f71ee533b3c9e1c3/href">https://medium.com/media/fc197c7df8438d87f71ee533b3c9e1c3/href</a></iframe><pre>Note : The length of factoradic representation should be equal to the length of the character array. Prepend zeros to ensure the length is same.</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9c81e34ab0c8" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>